A binary heap is a complete binary tree and possesses an interesting property called a heap property. The heap property states that every node in a binary tree must follow a specific order. There are two types of heaps depending upon how the nodes are ordered in the tree.
max-heap: In max-heap, a parent node is always larger than or equal to its children nodes.
min-heap: In min-heap, a parent node is always smaller than or equal to its children nodes.
Figure 1 shows an example of a max and min heap.
Since binary heap is a complete binary tree, the height of the tree is always O(log n). This is very important because most of the operations we perform in the binary heap scan the tree from top to bottom or bottom to top which leads to complexity of O(log n). This helps us to efficiently implement one sorting algorithm called heap sort and a priority queue.
A binary heap can be efficiently implemented using an array (static or dynamic). To implement a binary heap of height h, we need O(2^{h}) memory blocks and we insert the items in the array following level-order (breadth first) of a tree. Figure 2 shows the array implementation of a tree shown in Figure 1 (left).
The parent, the left child, and the right of a node at i can be calculated as
Parent = (i - 1) / 2 (Take floor).
Left Child = 2*i + 1
Right Child = 2*i + 2
Operations on a binary heap
The various operations on a binary heap are given in detail below. Please note that I am describing the max-heap here but with a little modification this can be changed to min-heap.
Insertion
The new item is initially inserted at the end of the heap (at the last position of the array). If it satisfies the heap property then we are done. Otherwise, we shift it up in the tree as long as it violates the heap property. The algorithm for inserting is given below.
1. Insert the new item at the end of the heap.
2. Compare the newly inserted item with its parent.
If the parent is larger, stop. If the parent is smaller, swap the item with its parent.
3. Repeat step 2 until the parent is larger or equal to the item.
Figure 3 shows the steps of inserting an item in an example heap.
In order to insert a new item, in the worst case, we need to travel all the way to the root item. Therefore, the complexity of the insertion operation is O(log n).
Delete Max
In a max heap, the first item is always the maximum. So to delete the maximum, we delete the first item. After the deletion of the first time, we replace the vacant first position by the last time in the array. We might need to shift this item down in order to keep the heap property intact. The algorithm is given below.
1. Store the first time in the tree in some temporary variable.
2. Replace the first node with the item in the last node.
3. Check the first node with its children nodes.
If the left child is larger, we swap it with the left child.
If the right node is larger, we swap it with the right node.
4. Repeat step 3 until the parent node is larger than the left and right child node.
5. Return the maximum value (stored in the temporary variable).
Step 3 and 4 in the above algorithm is called a max heapify (or bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down). This step moves the item down in the tree to its appropriate place. Figure 4 shows an example of this process.
As the insertion step, the complexity of delete max operation is O(log n).
Building a heap
We can build the heap from an array of n items using two methods. In the first method, we successively perform the insert operation on the heap. In n insert operations, we can build the heap from the array. Since each insert operation takes O(log n) time and there are n such operations, the complexity of this method is O(nlog n).
Another method does this in linear time. In this method, the internal node of the tree is max-heapified one at a time. If there are n items in the array, we start from the item at n/2 position and heapify it and we move to next item and do the same all the way down to the first item in the array. Consider a tree given in figure 5.
There are 10 nodes in the tree. Since the tree is a complete binary tree there are n/2 (floor) leaf nodes. We ignore all the leaf nodes and heapify the internal nodes. Using this method, we can build the heap in linear time O(n). The algorithm for this method is given below.
build-max-heap(arr) {
n = length of arr;
for (i = n/2; i > 0; i--) {
max-heapify(arr, i);
}
}
Implementation
The implementation of heap in C, C++, and Java is given below.
// returns the index of the parent node intparent(int i){ return (i - 1) / 2; }
// return the index of the left child intleft_child(int i){ return2*i + 1; }
// return the index of the right child intright_child(int i){ return2*i + 2; }
voidswap(int *x, int *y){ int temp = *x; *x = *y; *y = temp; }
// insert the item at the appropriate position voidinsert(int a[], int data, int *n){ if (*n >= MAX_SIZE) { printf("%s\n", "The heap is full. Cannot insert"); return; } // first insert the time at the last position of the array // and move it up a[*n] = data; *n = *n + 1;
// move up until the heap property satisfies int i = *n - 1; while (i != 0 && a[parent(i)] < a[i]) { swap(&a[parent(i)], &a[i]); i = parent(i); } }
// moves the item at position i of array a // into its appropriate position voidmax_heapify(int a[], int i, int n){ // find left child node int left = left_child(i);
// find right child node int right = right_child(i);
// find the largest among 3 nodes int largest = i;
// check if the left node is larger than the current node if (left <= n && a[left] > a[largest]) { largest = left; }
// check if the right node is larger than the current node if (right <= n && a[right] > a[largest]) { largest = right; }
// swap the largest node with the current node // and repeat this process until the current node is larger than // the right and the left node if (largest != i) { int temp = a[i]; a[i] = a[largest]; a[largest] = temp; max_heapify(a, largest, n); }
}
// converts an array into a heap voidbuild_max_heap(int a[], int n){ int i; for (i = n/2; i >= 0; i--) { max_heapify(a, i, n); } }
// returns the maximum item of the heap intget_max(int a[]){ return a[0]; }
// deletes the max item and return intextract_max(int a[], int *n){ int max_item = a[0];
// replace the first item with the last item a[0] = a[*n - 1]; *n = *n - 1;
// maintain the heap property by heapifying the // first item max_heapify(a, 0, *n); return max_item; }
// prints the heap voidprint_heap(int a[], int n){ int i; for (i = 0; i < n; i++) { printf("%d\n", a[i]); } printf("\n"); }
classBinaryHeap { private: conststaticint MAX_SIZE = 15; int heap[MAX_SIZE]; int size;
public: BinaryHeap() { size = 0; }
// returns the index of the parent node staticintparent(int i){ return (i - 1) / 2; }
// return the index of the left child staticintleftChild(int i){ return2*i + 1; }
// return the index of the right child staticintrightChild(int i){ return2*i + 2; }
staticvoidswap(int *x, int *y){ int temp = *x; *x = *y; *y = temp; }
// insert the item at the appropriate position voidinsert(int data){ if (size >= MAX_SIZE) { cout<<"The heap is full. Cannot insert"<<endl; return; }
// first insert the time at the last position of the array // and move it up heap[size] = data; size = size + 1;
// move up until the heap property satisfies int i = size - 1; while (i != 0 && heap[BinaryHeap::parent(i)] < heap[i]) { BinaryHeap::swap(&heap[BinaryHeap::parent(i)], &heap[i]); i = BinaryHeap::parent(i); } }
// moves the item at position i of array a // into its appropriate position voidmaxHeapify(int i){ // find left child node int left = BinaryHeap::leftChild(i);
// find right child node int right = BinaryHeap::rightChild(i);
// find the largest among 3 nodes int largest = i;
// check if the left node is larger than the current node if (left <= size && heap[left] > heap[largest]) { largest = left; }
// check if the right node is larger than the current node // and left node if (right <= size && heap[right] > heap[largest]) { largest = right; }
// swap the largest node with the current node // and repeat this process until the current node is larger than // the right and the left node if (largest != i) { int temp = heap[i]; heap[i] = heap[largest]; heap[largest] = temp; maxHeapify(largest); }
}
// returns the maximum item of the heap intgetMax(){ return heap[0]; }
// deletes the max item and return intextractMax(){ int maxItem = heap[0];
// replace the first item with the last item heap[0] = heap[size - 1]; size = size - 1;
// maintain the heap property by heapifying the // first item maxHeapify(0); return maxItem; }
// prints the heap voidprintHeap(){ for (int i = 0; i < size; i++) { cout<<heap[i]<<endl; } cout<<endl; } };
// returns the index of the parent node publicstaticintparent(int i){ return (i - 1) / 2; }
// return the index of the left child publicstaticintleftChild(int i){ return2*i + 1; }
// return the index of the right child publicstaticintrightChild(int i){ return2*i + 2; }
// insert the item at the appropriate position publicvoidinsert(int data){ if (size >= MAX_SIZE) { System.out.println("The heap is full. Cannot insert"); return; }
// first insert the time at the last position of the array // and move it up heap[size] = data; size = size + 1;
// move up until the heap property satisfies int i = size - 1; while (i != 0 && heap[BinaryHeap.parent(i)] < heap[i]) { int temp = heap[i]; heap[i] = heap[parent(i)]; heap[parent(i)] = temp; i = BinaryHeap.parent(i); } }
// moves the item at position i of array a // into its appropriate position publicvoidmaxHeapify(int i){ // find left child node int left = BinaryHeap.leftChild(i);
// find right child node int right = BinaryHeap.rightChild(i);
// find the largest among 3 nodes int largest = i;
// check if the left node is larger than the current node if (left <= size && heap[left] > heap[largest]) { largest = left; }
// check if the right node is larger than the current node // and left node if (right <= size && heap[right] > heap[largest]) { largest = right; }
// swap the largest node with the current node // and repeat this process until the current node is larger than // the right and the left node if (largest != i) { int temp = heap[i]; heap[i] = heap[largest]; heap[largest] = temp; maxHeapify(largest); }
}
// returns the maximum item of the heap publicintgetMax(){ return heap[0]; }
// deletes the max item and return publicintextractMax(){ int maxItem = heap[0];
// replace the first item with the last item heap[0] = heap[size - 1]; size = size - 1;
// maintain the heap property by heapifying the // first item maxHeapify(0); return maxItem; }
// prints the heap publicvoidprintHeap(){ for (int i = 0; i < size; i++) { System.out.print(heap[i] + " "); } System.out.println(); }
publicstaticvoidmain(String [] args){ BinaryHeap heap = new BinaryHeap(); } }