Binary Heap: The basics & Implementations
A binary heap is a complete binary tree which has the heap property. The binary heap was introduced by J. W. J. Williams in 1964 as a data structure for heap sort.
Complete Binary Tree
It is a kind of binary tree where all the levels, except possibly the last one are fully filled, and if the last level is not fully filled, it is filled from left to right.
Array Representation of Binary Heap
The complete binary tree or the binary heap has an interesting property. Let’s give an index to each node of the above binary tree. The indexes will be given as level wise.
Now if we notice carefully, it can be seen that for a node at index i the child nodes are at index 2i+1 and 2i+2 and the parent of the node is at index floor((i-1)/2). Using this property the heap can be stored in an array. The root of a heap will be at index 0. So the array representation of the above binary heap will be:
Next, we’ll try to know about the heap operations. As we all know, there are two types of heap — min-heap and max-heap. For simplicity, we’ll discuss the min-heap only.
Operations on a min-heap
There are two basic operations on a heap. The insert operation and the extract operation.
insert operation: With this operation, a node is added in the heap. After adding, to preserve the heap property, an up-heap or bubble-up or swim-up or heapify-up operation is performed if needed. The insertion is performed in the following manners:
1. Add the new node in the bottom level as the last node of the heap.
2. Compare the added node with its parent. If the parent is smaller than the added node, stop! The heap property is reserved.
3. And if the added node is smaller then its parent node, swap the nodes and continue from step 2.
The process is illustrated in the figure:
Extract operation: With this operation, the root or the minimum key of the heap is extracted or deleted. After deleting, to preserve the heap property, a down-heap or bubble-down or sink-down or heapify-down operation is performed if needed. The extraction is performed in the following manner:
1. Swap the root and the last node of the last level and remove the new last node.
2. Compare the new root with the children. If the heap property is reserved, Stop!
3. Swap the root with the smallest child and go to step 2.
The process is illustrated in the figure:
That’s it! Now we can go on and implement heap and heap operations.
Implementing heap using C++
We are going to implement the min-heap using an array. Let’s at first do the essential things and create an integer constant HEAP_SIZE which will hold the maximum size of the heap. Then create an integer array heap[HEAP_SIZE] which will hold the heap nodes.
Now, we’ll create a global integer variable s, which will hold the current size of the heap. We’ll create a function insert() for inserting a new node in the heap. It’ll be added as the last node. Then we’ll do bubble-up by calling the bubble_up() function. It’ll recursively call itself and will keep bubbling-up the inserted node until the heap property is reserved.
Now let’s create another function extract() which will extract the root. We’ll create one more function named bubble_down() which will recursively call itself and will keep bubbling down the swapped root until the heap property is reserved.
These are the basic operations. We can create an optional function get_root() which will return the minimum value i.e. the root value of the heap.
That’s it. You can find the full implementation here. Thank you very much. Let me know your thoughts.
Note: This is not an optimized or finely tuned implementation. This implementation needs to be tuned for some corner cases.
