Min-Heap and Max-Heap
Chapter Eighty-Three
Syllabus topic Module 2, "Priority Queues & Heaps: types of heaps"
Pages 262 to 264 of 411
In one line
A min-heap keeps the smallest value at the root and a max-heap the largest, and they are the same structure with one comparison reversed.
The two types
| Min-heap | Max-heap | |
|---|---|---|
| Order property | every node is less than or equal to its children | greater than or equal |
| Root holds | the minimum | the maximum |
| Used for | costs, distances, deadlines, Huffman | scores, importance, heap sort |
| Finding the other extreme | O(n) | O(n) |
The last row is worth noting at once: a min-heap cannot find the maximum quickly. The largest value is somewhere among the leaves, and the structure says nothing about which. Finding it means scanning, and that is O(n). A structure needing both extremes needs two heaps, or a different structure.
One implementation, both types
class Heap:
"""One heap. `better(a, b)` decides which of two values belongs higher.
For a min-heap, better is 'a < b'. For a max-heap, 'a > b'. Nothing else
differs, which is the honest statement of the difference between them."""
def __init__(self, better):
self.better = better
self.items = []
def size(self):
return len(self.items)
def peek(self):
if not self.items:
raise IndexError("peek at an empty heap")
return self.items[0]
def insert(self, value):
self.items.append(value)
i = len(self.items) - 1
while i > 0:
parent = (i - 1) // 2
if self.better(self.items[i], self.items[parent]):
self.items[i], self.items[parent] = self.items[parent], self.items[i]
i = parent
else:
break
def remove(self):
if not self.items:
raise IndexError("remove from an empty heap")
best = self.items[0]
last = self.items.pop()
if self.items:
self.items[0] = last
i, n = 0, len(self.items)
while True:
left, right, winner = 2 * i + 1, 2 * i + 2, i
if left < n and self.better(self.items[left], self.items[winner]):
winner = left
if right < n and self.better(self.items[right], self.items[winner]):
winner = right
if winner == i:
break
self.items[i], self.items[winner] = self.items[winner], self.items[i]
i = winner
return best
def holds(self):
"""The order property, checked."""
n = len(self.items)
for i in range(n):
for child in (2 * i + 1, 2 * i + 2):
if child < n and self.better(self.items[child], self.items[i]):
return False
return True
values = [15, 3, 17, 9, 11, 25, 30, 12, 5]
for name, better in (("min-heap", lambda a, b: a < b),
("max-heap", lambda a, b: a > b)):
heap = Heap(better)
for value in values:
heap.insert(value)
print("%s" % name)
print(" array :", heap.items)
print(" root :", heap.peek())
print(" order holds :", heap.holds())
drained = []
while heap.size():
drained.append(heap.remove())
print(" drained :", drained)
print()
print("values :", values)
print("sorted :", sorted(values))
print("reverse :", sorted(values, reverse=True))min-heap
array : [3, 5, 17, 9, 11, 25, 30, 15, 12]
root : 3
order holds : True
drained : [3, 5, 9, 11, 12, 15, 17, 25, 30]
max-heap
array : [30, 12, 25, 11, 9, 15, 17, 3, 5]
root : 30
order holds : True
drained : [30, 25, 17, 15, 12, 11, 9, 5, 3]
values : [15, 3, 17, 9, 11, 25, 30, 12, 5]
sorted : [3, 5, 9, 11, 12, 15, 17, 25, 30]
reverse : [30, 25, 17, 15, 12, 11, 9, 5, 3]Min-Heap and Max-Heap
One class, two heaps, differing by a single lambda. The min-heap drains in ascending order and the max-heap in descending, and both match Python's sorted exactly.
That draining is heap sort, and it is worth naming: inserting n items and removing them all gives them in order, at a cost of O(n log n). It is not on this syllabus as a topic of its own, but it falls out of the structure and an examiner may ask what it is called.
Converting between them
Three ways, and an examiner may ask for one:
Negate the keys. Store -x in a min-heap and it behaves as a max-heap for x. This is how Python's heapq, which only offers a min-heap, is used as a max-heap.
Reverse the comparison, which is what this chapter's class does.
Rebuild. Take the values out and build the other type, O(n) by chapter 85.
import heapq
values = [15, 3, 17, 9, 11, 25, 30]
min_heap = list(values)
heapq.heapify(min_heap)
max_heap = [-v for v in values]
heapq.heapify(max_heap)
print("heapq offers only a min-heap.")
print(" smallest, directly :", min_heap[0])
print(" largest, by negation :", -max_heap[0])
print()
print("draining the negated heap and flipping the sign:")
out = []
while max_heap:
out.append(-heapq.heappop(max_heap))
print(" ", out)
print(" which is descending:", out == sorted(values, reverse=True))heapq offers only a min-heap.
smallest, directly : 3
largest, by negation : 30
draining the negated heap and flipping the sign:
[30, 25, 17, 15, 11, 9, 3]
which is descending: TrueOther types of heap, named
MU's label says "types of heaps", and if an examiner wants more than min and max, these are the standard answers:
Binary heap. What this chapter builds: each node has at most two children. The default. d-ary heap. Each node has d children. Shallower, so insertion is faster and removal slower. Binomial heap and Fibonacci heap. Support merging two heaps efficiently, which a binary heap cannot do better than O(n). The Fibonacci heap gives O(1) amortised decrease-key, which improves Dijkstra's algorithm in theory.
All but the binary heap are outside this paper. Knowing the names and the one-line reason is enough.
Quick revision
- Min-heap: every node is less than or equal to its children, and the root is the minimum. Max-heap: the
reverse.
- They are the same structure with one comparison reversed, which is why one implementation with a
Min-Heap and Max-Heap
comparison parameter gives both.
- A min-heap cannot find the maximum in better than O(n), and vice versa.
- Draining a heap gives the values in order: that is heap sort, O(n log n).
- To get a max-heap from a min-heap library, negate the keys.
- Other types: binary (the default), d-ary, binomial and Fibonacci, the last two for efficient merging.
Test yourself
1. Give the order property of each type and say what the root holds. Min-heap: every node is less than or equal to its children, and the root is the minimum. Max-heap: every node is greater than or equal to its children, and the root is the maximum.
2. How much work is it to find the largest value in a min-heap? O(n). The largest is somewhere among the leaves and the structure gives no clue which, so it must be scanned for.
3. How do the two implementations differ? By one comparison. Writing the heap with the comparison passed in gives both types from one piece of code.
4. What is produced by inserting n values and then removing them all, and what is it called? The values in sorted order, ascending from a min-heap and descending from a max-heap. It is heap sort, and it costs O(n log n).
5. Python's heapq offers only a min-heap. How is a max-heap obtained from it? By negating the keys on the way in and negating them again on the way out.
6. Name two other types of heap and what they are for. Binomial and Fibonacci heaps, which support merging two heaps efficiently; a d-ary heap, which is shallower and trades faster insertion for slower removal.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.