Data Structures & Algorithms · Part 2
Sep 3, 2023
4 min read
Heap Data Structures (Part 2)
Prerequisites
Before diving into the implementation details, I highly recommend going through Part 1 of this series to understand the theory, array indices, and bubbling operations of heaps.
In this part, we will implement a complete, functional min-heap in C++.
Implementation Details
We will focus on implementing a min-heap. A max-heap follows the exact same structure, only with reversed comparison operators.
There are three primary operations:
1. Creating a min-heap from an unsorted array.
2. Adding an element to the min-heap.
3. Removing the minimum element from the min-heap.
Each of these operations relies on two fundamental helper functions: heapifyUp (bubbling up) and heapifyDown (bubbling down).
First, let's establish our index-mapping helper functions:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Print heap elements sequentially
void printMinHeap(const vector<int>& arr) {
for (int val : arr) {
cout << val << " ";
}
cout << "\n";
}
// Get parent and child indices using array mappings
int getLeftChildIndex(int parentIndex) {
return parentIndex * 2 + 1;
}
int getRightChildIndex(int parentIndex) {
return parentIndex * 2 + 2;
}
int getParentIndex(int childIndex) {
return (childIndex - 1) / 2;
}
1. HeapifyUp (Bubble Up)
When we insert a new element, it is placed at the end of the array. If it is smaller than its parent, we bubble it up by swapping it with its parent. We repeat this process until the element is in a valid position (greater than or equal to its parent, or at the root).
void heapifyUp(vector<int>& arr, int index) {
int parentIndex = getParentIndex(index);
// Bubble up as long as we haven't hit the root and parent is larger
while (index > 0 && arr[index] < arr[parentIndex]) {
swap(arr[parentIndex], arr[index]);
index = parentIndex;
parentIndex = getParentIndex(index);
}
}
2. HeapifyDown (Bubble Down)
When we remove the minimum element, we swap the root with the last element of the array. To restore order, we bubble it down: we compare it with its left and right children and swap it with the smaller of the two. We repeat this until the node is smaller than both its children.
void heapifyDown(vector<int>& arr, int parentIndex) {
int n = arr.size();
int leftChildIndex = getLeftChildIndex(parentIndex);
while (leftChildIndex < n) {
int smallerChildIndex = leftChildIndex;
int rightChildIndex = getRightChildIndex(parentIndex);
// Determine the smaller child
if (rightChildIndex < n && arr[rightChildIndex] < arr[smallerChildIndex]) {
smallerChildIndex = rightChildIndex;
}
// If parent is already smaller than the smallest child, heap is valid
if (arr[parentIndex] <= arr[smallerChildIndex]) {
break;
}
swap(arr[parentIndex], arr[smallerChildIndex]);
parentIndex = smallerChildIndex;
leftChildIndex = getLeftChildIndex(parentIndex);
}
}
High-Level Operations
Now that our helper functions are defined, we can implement the main heap operations:
Creating a Min-Heap from an Unsorted Array
To construct a min-heap from an unsorted array, we call heapifyDown on all elements, starting from the last non-leaf node back to the root. We can skip leaf nodes because they have no children to bubble down into. The last non-leaf node is the parent of the last element: n / 2 - 1.
void createMinHeap(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyDown(arr, i);
}
}
Adding an Element
To insert a node, we append it to the end of the vector and bubble it up to its correct position.
void addElement(vector<int>& arr, int newEle) {
arr.push_back(newEle);
heapifyUp(arr, arr.size() - 1);
}
Removing the Minimum Element
To remove the root, we swap it with the last element in the vector, remove it from the end, and bubble the new root down.
void removeElement(vector<int>& arr) {
if (arr.empty()) return;
int n = arr.size();
swap(arr[0], arr[n - 1]);
arr.pop_back();
heapifyDown(arr, 0);
}
Verification and Execution
You can run and test this code live on Ideone.
int main() {
vector<int> arr = {10, 22, 32, 6, 25, 22, 15, 56, 65, 72};
cout << "Unsorted array: ";
printMinHeap(arr);
cout << "Min-Heap constructed: ";
createMinHeap(arr);
printMinHeap(arr);
// Output: 6 10 15 22 25 22 32 56 65 72
cout << "Inserting 8: ";
addElement(arr, 8);
printMinHeap(arr);
// Output: 6 8 15 22 10 22 32 56 65 72 25
cout << "Removing min element: ";
removeElement(arr);
printMinHeap(arr);
// Output: 8 10 15 22 25 22 32 56 65 72
cout << "Removing next min: ";
removeElement(arr);
printMinHeap(arr);
// Output: 10 22 15 56 25 22 32 72 65
return 0;
}
