Binary Heaps
The most common encoding of a priority queue is structure called a binary heap.
It's a tree structure that organizes data in a different way than BSTs.
A binary min-heap is a binary tree such that
- Structure Property: The tree is complete.
- Every level except (possibly) the last is full.
- The last level is filled in from left to right.
- Order Property: There are two kinds of heaps: min-heaps (which have the smallest element at the top) and max-heaps (which have the largest).
- In a min-heap, the key in every node is at least as small as all of its children.
- In a max-heap, the key in every node is at least as big as all of its children.
We'll focus on min-heaps in our discussions.
Is each subtree also a heap?
Yes, that's implied by our rules above!
The picture below shows a heap—in this case, it only shows the keys (we can just assume that every node contains an associated value as well).
Notice that left and right are not relevant to how the data is organized, just above and below.
Does this heap anything to do with the heap we use for
new
anddelete
? Is that this kind of heap?No. “The Heap” is a region of program memory, and has no relationship to the binary-heap data structure.
Meh. It's like names were in short supply or something.
Representing a Heap
Although we visualize a heap as a binary tree, in practice we don't usually encode it using nodes and pointers.
Instead, the structure property of a heap allows us to represent it using an array!
Hay! How do you represent a tree with an array?
Well, this isn't just any tree. It's a complete tree.
Since it has no gaps, a level-order traversal tells us everything we need to know!
We would typically encode the binary heap shown above as the level-order traversal of its elements.
A level-order traversal lists all the nodes in each layer from top to bottom, going left to right within each layer.
In general, the node at index \( i \) has its
- Left cildren at index \( 2i + 1 \)
- Right child at index \( 2i + 2 \)
- Parent at index \( \lfloor (i - 1) / 2 \rfloor \) (where \( \lfloor x \rfloor \) is the floor function, which rounds down to the nearest integer).
Woah! This array-based encoding has a lot less space overhead than having all those pointers to nodes and so on.
It will also have some runtime efficiency benefits, as we will see!
Getting the Minimum Element
Because of the heap property that the key in a node is always the smallest in its subtree, we know that the minimum key must be in the root!
The root of the tree is stored at index 0 in the array, so we can access it in \( \Theta(1) \) time.
That's so simple! Always access index 0!
Easy access to the minimum element is the whole point of a binary heap!
Now the trick is to maintain these properties as items are inserted/removed.
(When logged in, completion status appears here.)