Data Structure (6) - Heaps & Priority Queues
ADT
- insert(value)
- remove()
- isEmpty()
Where value is among int, string, double, char... or objects that supports < operator.
Heap
Unsorted Array: O(1)* insert, O(n) removeMin (need to find min first)
Unsorted Linked List: O(1) insert, O(n) removeMin
Sorted Array: O(n)* insert, O(1) removeMin
Sorted Linked List: O(n) insert, O(1) removeMin
It's easier to removeMin on sorted structures and insert on unsorted structures.
To balance the worst case time to O(lg(n)) insert and O(lg(n)) removeMin, we could use a binary tree.
Definition
(min-)Heap
A complete binary tree t is a min-heap if:
- T = {} or
- T = {r, TL, TR} where r is less than roots of {TL , TR} and {TL , TR} are min-heaps.
Logically it's a tree, and implementation-wise, it's an array.
The heap above in array would be: [1, 4, 5, 12, 7, 6, 8, 13, 14, null, null, 11, null, null, null]
We could define left must be larger or smaller than right, but as long as all roots are smaller than their children, it's a min-heap.
Priority queues are based on heaps.
Operations
- Left child of node[i]: node[2*i]
- Right child of node[i]: node[2*i + 1]
- Parent of node[i]: floor(i/2)
We could also store the number of nodes, n, in node[0], and the above remains the same. Knowing the number of nodes can help you know where in the array is outside of the heap.
How to Insert
template <class T>
void Heap<T>::_insert(const T & key) {
// check if there's enough space
if (size_ == capacity) {
_growArray();
}
// insert element at the end of array
item_[++size] = key;
// restore heap property
_heapifyUp();
}
template <class T>
void Heap<T>::_heapifyUp(size_t index) {
if(index>1) { // 1 is the root here, as we stored size in 0
if(item_[index] < item_[parent(index)]) {
std::swap(item_[index], item_[parent(index));
_heapifyUp(parent(index));
}
}
}
How to Remove
removeMin() is removing root of a min-heap, and removeMax() is removing root of a max-heap.
When removing root:
- Swap root with the last node.
- Remove the last node (root).
- Heapify to restore heap property
template <class T>
T Heap<T>::_remove() {
T min_value = item_[1];
item_[1] = item_[size--]; // swap with last and delete
_heapifyDown();
return min_value; // return original root value
}
template <class T>
void Heap<T>::_heapifyDown(size_t index=1) {
if(!_isLeaf(index)) {
size_t minChildIndex = _minChild(index);
if(item_[index] > item_[minChildIndex]) {
std::swap(item_[index], item_[minChildIndex]);
_heapifyDown(minChildIndex);
}
}
}
How to Build a Heap
buildHeap - heapifyUp: O(n*log(n)) – each insert is O(log(n))
void Heap<T>::buildHeap() {
for(unsigned i=2; i<= size_; i++) {
heapifyUp(i);
// takes O(n logn)
}
}
buildHeap - heapifyDown: O(n) – takes time of O(sum of the height of all sub trees)
void Heap<T>::buildHeap() {
for(unsigned i=parent(size_); i>0; i--) {
heapifyDown(i);
// takes O(n)
}
}
Prove heap building running time:
- S(h): Sum of heights of all nodes in a complete tree of h
- S(0) = 0
- S(1) = 1 + 0 + 0 = 1
- S(2) = 2 + 1 + 1 = 4
- ....
- S(h) = h + 2 * S(h-1) = 2(h+1) -h - 2
- Since h<=lg(n),
- O(2(lg(n)+1) - lg(n) -2) = O(n-2-lg(n)) = O(n)