The Heap: Shape and Order
Chapter Eighty-One
Syllabus topic Module 2, "Priority Queues & Heaps: Heaps"
Pages 255 to 257 of 411
In one line
A heap is a complete binary tree in which every node is at least as good as its children, which is enough to put the best item at the root and loose enough to be maintained in O(log n).
The two properties
A heap satisfies both of these, and neither alone is enough.
1. The shape property: it is a complete binary tree. Every level is full except possibly the last, which fills from the left with no gaps. Chapter 56's exact word.
2. The order property (the heap property): every node is at least as good as both its children. For a min-heap, every node is less than or equal to its children. For a max-heap, greater than or equal.
What the order property does NOT say
This is where students lose marks.
It says nothing about siblings. Two children of the same node are in no particular order relative to each other.
It says nothing about cousins. A node deep on the left may be smaller than a node high on the right.
A heap is therefore not sorted, and its inorder traversal means nothing. Only the path from any node up to the root is ordered.
import heapq
values = [15, 3, 17, 9, 11, 25, 30, 12, 5]
heap = list(values)
heapq.heapify(heap)
print("values :", values)
print("as a heap:", heap)
print("sorted :", sorted(values))
print()
print("the heap array is NOT sorted:", heap != sorted(values))
print("but the smallest value IS at the front:", heap[0] == min(values))
print()
print("reading the heap level by level:")
level, index = 0, 0
while index < len(heap):
count = 2 ** level
print(" level %d: %s" % (level, heap[index:index + count]))
index += count
level += 1
print()
print("note level 1: %s. the two children of the root are in no order"
% (heap[1:3],))
print("relative to each other, and that is allowed.")values : [15, 3, 17, 9, 11, 25, 30, 12, 5]
as a heap: [3, 5, 17, 9, 11, 25, 30, 12, 15]
sorted : [3, 5, 9, 11, 12, 15, 17, 25, 30]
the heap array is NOT sorted: True
but the smallest value IS at the front: True
reading the heap level by level:
level 0: [3]
level 1: [5, 17]
level 2: [9, 11, 25, 30]
level 3: [12, 15]
note level 1: [5, 17]. the two children of the root are in no order
relative to each other, and that is allowed.The array is not sorted and the minimum is at the front. That is exactly as much order as a heap promises, and it is exactly as much as a priority queue needs.
Why "complete" and not something else
Chapter 56 separated three words, and the choice here is deliberate.
The Heap: Shape and Order
Not "perfect". A perfect tree has 1, 3, 7, 15 nodes only, so a heap could never hold 10 items.
Not "full". A full tree may have a gap in the middle of a level, which breaks the array arithmetic of chapter 82.
Complete is exactly right. It admits any number of items, there is exactly one complete shape for each size (chapter 56 measured that), and it has no gaps, so the tree can live in an array with no pointers.
Why this much order and no more
The alternative would be to keep the tree fully sorted, which is a binary search tree. Why not?
Because a search tree answers a question nobody asked here. A priority queue needs one thing: the best item. A search tree maintains enough order to find any item, and that extra order costs more to maintain, and would rule out the array representation.
The heap keeps exactly the order needed for "what is best" and no more. That is why insertion and removal are O(log n) with small constants and why the structure has no pointers at all.
| Binary search tree | Heap | |
|---|---|---|
| Order maintained | total: every node against every other | partial: each node against its children |
| Find an arbitrary value | O(log n) | O(n) |
| Find the best value | O(log n) | O(1) |
| Shape | any, and must be balanced deliberately | always complete, automatically |
| Representation | nodes with two pointers | an array, no pointers |
| In sorted order | inorder walk, free | not possible without emptying it |
Both properties, checked
import heapq
import random
def shape_property(heap):
"""A list IS complete by construction: there are no gaps in a list.
What must be checked is that every index below the length is occupied."""
return all(item is not None for item in heap)
def order_property(heap):
"""Every node is <= its children, for a min-heap."""
for i in range(len(heap)):
for child in (2 * i + 1, 2 * i + 2):
if child < len(heap) and heap[i] > heap[child]:
return False, (i, child)
return True, None
random.seed(8)
for trial in range(5):
values = random.sample(range(1000), 12)
heap = list(values)
heapq.heapify(heap)
ok, where = order_property(heap)
print("trial %d: shape %-5s order %-5s root is the minimum: %s"
% (trial + 1, shape_property(heap), ok, heap[0] == min(values)))
print()
not_a_heap = [3, 5, 17, 9, 11, 25, 30, 12, 2]
ok, where = order_property(not_a_heap)
print("a deliberately broken heap:", not_a_heap)
print(" order property holds:", ok)
print(" index %d holds %d and its child at %d holds %d"
% (where[0], not_a_heap[where[0]], where[1], not_a_heap[where[1]]))trial 1: shape True order True root is the minimum: True
trial 2: shape True order True root is the minimum: True
trial 3: shape True order True root is the minimum: True
trial 4: shape True order True root is the minimum: True
trial 5: shape True order True root is the minimum: True
a deliberately broken heap: [3, 5, 17, 9, 11, 25, 30, 12, 2]
order property holds: False
index 3 holds 9 and its child at 8 holds 2The Heap: Shape and Order
Five random heaps pass both properties, and a deliberately broken one is caught with the exact pair of indices that violate it. A checker that never reports a failure is not a checker, which is why the broken case is included.
Quick revision
- A heap has two properties: the shape property (it is a complete binary tree) and the order property
(every node is at least as good as its children).
- Min-heap: every node is less than or equal to its children. Max-heap: greater than or equal.
- The order property says nothing about siblings or cousins, so a heap is NOT sorted and its inorder
traversal is meaningless. Only root-to-node paths are ordered.
- Complete is the exact word: perfect would restrict the size to 1, 3, 7, 15; full would allow a gap and
break the array arithmetic.
- A heap keeps exactly the order needed to answer "what is best" and no more, which is why it is cheaper
than a search tree and needs no pointers.
- Finding the best is O(1); finding an arbitrary value is O(n).
Test yourself
1. State the two properties of a heap. The shape property: it is a complete binary tree. The order property: every node is at least as good as both its children, meaning smaller for a min-heap and larger for a max-heap.
2. What does the order property say about two siblings? Nothing at all. Siblings are unordered relative to each other, as are cousins, which is why a heap is not sorted.
3. Why is "complete" the right shape requirement rather than "perfect" or "full"? Perfect would allow only sizes 1, 3, 7, 15 and so on. Full would permit a gap in the middle of a level, breaking the array index arithmetic. Complete admits any size, has exactly one shape per size, and has no gaps.
4. Where is the best item, and what does it cost to find? At the root, index 0 of the array, and it costs O(1).
5. Give two things a binary search tree can do that a heap cannot. Find an arbitrary value in O(log n) rather than O(n), and produce the items in sorted order without being emptied.
6. Why does a heap deliberately keep less order than a search tree? Because a priority queue only ever asks for the best item. Maintaining total order would cost more and would prevent the array representation, for an ability nothing here uses.
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.