A min-heap keeps its smallest element at the root: every parent has a value no larger than either child. Think of it as a priority queue where smaller numbers receive higher priority. section 10.13
A min-heap is useful when you need to:
- Extract the next-smallest element repeatedly. section 10.13
- Keep only the k best candidates while scanning n entries. section 10.21
- Implement the ordering rule through a priority function, such as priority(x) = -x when smaller values should appear first. section 10.13
Keeping the six largest entries
Scan the entries one by one while storing only six in a min-heap. The root is the least frequent item among the current six; when a new entry is better, remove that root and insert the new entry. This takes O(n*log(k)) steps and O(k) extra space. section 10.21
def k_largest_elements(arr, k):
heap = Heap(element_priority=lambda x: -x[1])
for i in range(len(arr)):
if len(heap) >= k:
if heap.peek()[1] < arr[i]:
heap.top() #1
heap.insert((i, arr[i]))
else:
heap.insert((i, arr[i]))
return [heap.top() for _ in range(k)]
print(k_largest_elements(drawn, 6))
#1 When we remove the smallest element, we don’t need the value. We just discard it.
The Python listing demonstrates a bounded min-heap using a custom priority function for selecting frequent entries. section 10.21
