Heap
Definition
中文稱為堆積，分為最大堆積(Max Heap)跟最小堆積(Min Heap)
Max Heap
- Is a complete binary tree
- All children are equal smaller then current node
Root Node會是最大值
Min Heap
- Is a complete binary tree
- All children are equal or larger then current node
Root Node會是最小值
Complexity of Operations
| Operation | Time | Space |
|---|---|---|
| Construct | O(N) | O(N) |
| Insert a Node | O(logN) | O(1) |
| Delete a Node | O(logN) | O(1) |
| Get the Max/Min | O(1) | O(1) |
| Get size | O(1) | O(1) |
Question Pattern
尋求最大(小)，或Nth大(小)的元素幾乎都可以靠Heap處理
Steps
- 依題目決定該用Max Heap或Min Heap
- Construct Heap
- Add all elements into Heap
- Pop N elements from Heap Root to reach the target
Implementation
Python
Construct Heap
# Push One by One, not effect to origin list
elements = [2,3,1,7,6,9]
heap = []
for elm in elements:
heapq.heappush(heap, elm)
# Or, transfer a list into heap in liner time
elements = [2,3,1,7,6,9]
heapq.heapify(elements) # elements now a heap
要小心的是，heappop, heappush 這些method只對heap有效果
直接拿list給他用不會exception，但pop的結果會錯誤
elements = [2,3,1,7,6,9] # elements is NOT a heap
print(elements) # [2,3,1,7,6,9]
heapq.heappop(elements) # 2
heapq.heappop(elements) # 3
heapq.heappop(elements) # 1
heapq.heappop(elements) # 7
初始化成heap後再進行heappop結果才會正確
elements = [2,3,1,7,6,9]
heapq.heapify(elements)
print(elements) # [2,3,1,7,6,9] 看起來不會有差 異，但資料結構已經改變
heapq.heappop(elements)
heapq.heappop(elements) # 1
heapq.heappop(elements) # 2
heapq.heappop(elements) # 3
heapq.heappop(elements) # 6
nlargest & nsmallest
拿Python刷題遇到heap最作弊的兩個function，直接拿可iter的物件做出heap並拿Nth largest/smallest
注意這兩個function的參數是iterable物件，也就是說construct和使用一次完成
拿出前n個最大的elements：heapq.nlargest(n, iterable, key=None)
elements = [2,3,1,7,6,9]
# Example: 拿前3大的element
heapq.nlargest(3, elements) # [9,7,6]
# Example: 拿第3大的element
heapq.nlargest(3, elements)[-1] # 6
# 要注意elements仍然是普通list，對他heappop會拿到錯誤結果
heapq.heappop(elements) # 2 (應該要是1)
拿出前n個最小的elements：heapq.nsmallest(n, iterable, key=None)
elements = [2,3,1,7,6,9]
# Example: 拿前2小的element
heapq.nsmallest(3, elements) # [1,2]
# Example: 拿第3小的element
heapq.nsmallest(3, elements)[-1] # 3