Heaps are powerful tree-based data structures designed for efficient priority handling, making them indispensable in optimization problems and real-time systems. Today’s exploration focused on understanding the heap property, implementing heaps using arrays, and solving practical problems that leverage their logarithmic time efficiency.
1. Implement Max Heap and Min Heap
This program implements a Max Heap and a Min Heap using arrays. Each heap maintains its respective property by reordering elements during insertion and extraction. The MaxHeap class ensures the largest element is always at the root, while MinHeap ensures the smallest element is at the root. Helper functions handle node indexing and maintain heap properties through heapify.
Code:
#include <iostream>
using namespace std;
class MaxHeap {
private:
int* heap;
int capacity;
int size;
// Helper functions
int parent(int i) { return (i - 1) / 2; }
int left_child(int i) { return 2 * i + 1; }
int right_child(int i) { return 2 * i + 1 + 1; }
void heapify(int i) {
int largest = i;
int left = left_child(i);
int right = right_child(i);
if (left < size && heap[left] > heap[largest])
largest = left;
if (right < size && heap[right] > heap[largest])
largest = right;
if (largest != i) {
swap(heap[i], heap[largest]);
heapify(largest);
}
}
public:
MaxHeap(int cap) {
capacity = cap;
size = 0;
heap = new int[capacity];
}
void insert(int value) {
if (size == capacity) {
cout << "Heap is full!" << endl;
return;
}
heap[size] = value;
int current = size;
size++;
while (current > 0 && heap[parent(current)] < heap[current]) {
swap(heap[current], heap[parent(current)]);
current = parent(current);
}
}
int extract_max() {
if (size <= 0) {
cout << "Heap is empty!" << endl;
return -1;
}
if (size == 1) {
size--;
return heap[0];
}
int root = heap[0];
heap[0] = heap[size - 1];
size--;
heapify(0);
return root;
}
int get_max() {
if (size <= 0) {
cout << "Heap is empty!" << endl;
return -1;
}
return heap[0];
}
};
class MinHeap {
private:
int* heap;
int capacity;
int size;
// Helper functions
int parent(int i) { return (i - 1) / 2; }
int left_child(int i) { return 2 * i + 1; }
int right_child(int i) { return 2 * i + 1 + 1; }
void heapify(int i) {
int smallest = i;
int left = left_child(i);
int right = right_child(i);
if (left < size && heap[left] < heap[smallest])
smallest = left;
if (right < size && heap[right] < heap[smallest])
smallest = right;
if (smallest != i) {
swap(heap[i], heap[smallest]);
heapify(smallest);
}
}
public:
MinHeap(int cap) {
capacity = cap;
size = 0;
heap = new int[capacity];
}
void insert(int value) {
if (size == capacity) {
cout << "Heap is full!" << endl;
return;
}
heap[size] = value;
int current = size;
size++;
while (current > 0 && heap[parent(current)] > heap[current]) {
swap(heap[current], heap[parent(current)]);
current = parent(current);
}
}
int extract_min() {
if (size <= 0) {
cout << "Heap is empty!" << endl;
return -1;
}
if (size == 1) {
size--;
return heap[0];
}
int root = heap[0];
heap[0] = heap[size - 1];
size--;
heapify(0);
return root;
}
int get_min() {
if (size <= 0) {
cout << "Heap is empty!" << endl;
return -1;
}
return heap[0];
}
};
int main() {
MaxHeap maxHeap(10);
maxHeap.insert(20);
maxHeap.insert(15);
maxHeap.insert(30);
maxHeap.insert(40);
maxHeap.insert(10);
cout << "Max Heap:" << endl;
cout << "Max Element: " << maxHeap.get_max() << endl;
cout << "Extract Max: " << maxHeap.extract_max() << endl;
cout << "Max Element after extraction: " << maxHeap.get_max() << endl;
MinHeap minHeap(10);
minHeap.insert(20);
minHeap.insert(15);
minHeap.insert(30);
minHeap.insert(40);
minHeap.insert(10);
cout << "Min Heap:" << endl;
cout << "Min Element: " << minHeap.get_min() << endl;
cout << "Extract Min: " << minHeap.extract_min() << endl;
cout << "Min Element after extraction: " << minHeap.get_min() << endl;
return 0;
}
Output:
2. K Largest Elements in an Array
This program finds the k largest elements in an array using a Min Heap implemented with a fixed-size array. First, it builds a Min Heap with the initial k elements of the array. Then, for each remaining element, if the element is larger than the root (smallest in the heap), the root is replaced, and the heap is restructured to maintain the Min Heap property. Finally, the heap contains the k largest elements.
Code:
#include <iostream>
#include <climits>
using namespace std;
// Helper function to maintain the Min Heap property
void heapify(int heap[], int size, int i) {
int smallest = i; // Initialize smallest as the root
int left = 2 * i + 1; // Left child index
int right = 2 * i + 2; // Right child index
// Check if left child is smaller than the root
if (left < size && heap[left] < heap[smallest])
smallest = left;
// Check if right child is smaller than the current smallest
if (right < size && heap[right] < heap[smallest])
smallest = right;
// If the smallest is not the root, swap and heapify
if (smallest != i) {
swap(heap[i], heap[smallest]);
heapify(heap, size, smallest);
}
}
// Function to build the Min Heap
void build_heap(int heap[], int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(heap, size, i);
}
}
// Function to find k largest elements using a Min Heap
void k_largest_elements(int arr[], int n, int k) {
if (k > n) {
cout << "Invalid value of k!" << endl;
return;
}
// Step 1: Build a Min Heap with the first k elements of the array
int heap[k];
for (int i = 0; i < k; i++) {
heap[i] = arr[i];
}
build_heap(heap, k);
// Step 2: Process the rest of the array
for (int i = k; i < n; i++) {
if (arr[i] > heap[0]) { // If the current element is larger than the root of the heap
heap[0] = arr[i]; // Replace the root
heapify(heap, k, 0); // Re-heapify the root
}
}
// Step 3: Print the k largest elements (Min Heap will store them)
cout << "The " << k << " largest elements are: ";
for (int i = 0; i < k; i++) {
cout << heap[i] << " ";
}
cout << endl;
}
// Main function to test the k largest elements function
int main() {
int arr[] = {10, 20, 11, 70, 60, 50, 30, 100};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
k_largest_elements(arr, n, k);
return 0;
}
Output:
3. Kth Smallest Element in a Matrix
This program finds the kth smallest element in a sorted matrix using a Min Heap. It initializes the heap with the first element of each row, then repeatedly extracts the smallest element from the heap k times. After each extraction, the next element from the same row (if available) is added to the heap to maintain the order. The kth extracted element is the result.
Code:
#include <iostream>
#include <queue>
#include <climits>
using namespace std;
#define MAX 100 // Define the maximum matrix size
struct HeapNode {
int value; // Matrix element value
int row; // Row index of the element
int col; // Column index of the element
};
void heapify(HeapNode heap[], int size, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && heap[left].value < heap[smallest].value)
smallest = left;
if (right < size && heap[right].value < heap[smallest].value)
smallest = right;
if (smallest != i) {
swap(heap[i], heap[smallest]);
heapify(heap, size, smallest);
}
}
// Function to extract the smallest element from the heap
HeapNode extract_min(HeapNode heap[], int &size) {
if (size <= 0) {
return {INT_MAX, -1, -1};
}
HeapNode root = heap[0];
heap[0] = heap[size - 1];
size--;
heapify(heap, size, 0);
return root;
}
// Function to insert a new element into the heap
void insert_heap(HeapNode heap[], int &size, HeapNode node) {
if (size >= MAX) {
cout << "Heap overflow!" << endl;
return;
}
heap[size] = node;
int current = size;
size++;
while (current != 0 && heap[(current - 1) / 2].value > heap[current].value) {
swap(heap[current], heap[(current - 1) / 2]);
current = (current - 1) / 2;
}
}
int kth_smallest(int matrix[MAX][MAX], int n, int k) {
HeapNode heap[MAX];
int heapSize = 0;
// Step 1: Insert the first element of each row into the heap
for (int i = 0; i < n && i < k; i++) {
insert_heap(heap, heapSize, {matrix[i][0], i, 0});
}
// Step 2: Extract the smallest element k times
HeapNode node;
for (int i = 0; i < k; i++) {
node = extract_min(heap, heapSize);
int nextCol = node.col + 1;
// If there is a next column in the same row, insert it into the heap
if (nextCol < n) {
insert_heap(heap, heapSize, {matrix[node.row][nextCol], node.row, nextCol});
}
}
return node.value;
}
int main() {
int matrix[MAX][MAX] = {
{10, 20, 30, 40},
{15, 25, 35, 45},
{25, 29, 37, 48},
{32, 33, 39, 50}
};
int n = 4;
int k = 7;
cout << "The " << k << "th smallest element is: " << kth_smallest(matrix, n, k) << endl;
return 0;
}
Output:
4. Merge K Sorted Arrays
This program merges k sorted arrays into a single sorted array using a Min Heap. It initializes the heap with the first element of each array. In each step, the smallest element is extracted from the heap and added to the result array. If the extracted element's array has more elements, the next element is inserted into the heap. This process continues until all elements are merged into the result array.
Code:
#include <iostream>
#include <climits>
using namespace std;
#define MAX 1000 // Define the maximum size for the heap
struct HeapNode {
int value; // Value of the current element
int arrayIdx; // Index of the array the element belongs to
int nextIdx; // Index of the next element in the array
};
// Function to maintain the Min Heap property
void heapify(HeapNode heap[], int size, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && heap[left].value < heap[smallest].value)
smallest = left;
if (right < size && heap[right].value < heap[smallest].value)
smallest = right;
if (smallest != i) {
swap(heap[i], heap[smallest]);
heapify(heap, size, smallest);
}
}
// Function to merge k sorted arrays
void merge_arrays(int arrays[][MAX], int sizes[], int k, int result[], int &resultSize) {
HeapNode heap[MAX];
int heapSize = 0;
// Step 1: Insert the first element of each array into the heap
for (int i = 0; i < k; i++) {
if (sizes[i] > 0) { // Check if the array is not empty
heap[heapSize++] = {arrays[i][0], i, 1}; // Insert first element
}
}
// Build the initial Min Heap
for (int i = heapSize / 2 - 1; i >= 0; i--) {
heapify(heap, heapSize, i);
}
// Step 2: Extract elements and build the merged array
resultSize = 0;
while (heapSize > 0) {
// Extract the smallest element from the heap
HeapNode root = heap[0];
result[resultSize++] = root.value;
// If there are more elements in the array, insert the next element
if (root.nextIdx < sizes[root.arrayIdx]) {
heap[0] = {arrays[root.arrayIdx][root.nextIdx], root.arrayIdx, root.nextIdx + 1};
} else { // If no more elements in the array, reduce the heap size
heap[0] = heap[--heapSize];
}
// Re-heapify the heap
heapify(heap, heapSize, 0);
}
}
// Main function to test the merge function
int main() {
int arrays[3][MAX] = {
{1, 4, 7, 10},
{2, 5, 8},
{3, 6, 9, 12, 15}
};
int sizes[] = {4, 3, 5}; // Sizes of the individual arrays
int k = 3; // Number of arrays
int result[MAX];
int resultSize;
merge_arrays(arrays, sizes, k, result, resultSize);
cout << "Merged array: ";
for (int i = 0; i < resultSize; i++) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}
Output:
5. Find Median From a Data Stream
Code:
#include <iostream>
#include <queue>
#include <functional>
using namespace std;
#define MAX 1000 // Maximum size for the heaps
class MedianFinder {
private:
int maxHeap[MAX]; // Max Heap to store the smaller half of the numbers
int minHeap[MAX]; // Min Heap to store the larger half of the numbers
int maxHeapSize; // Current size of Max Heap
int minHeapSize; // Current size of Min Heap
// Helper functions for Max Heap
void max_heapify(int idx) {
int largest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < maxHeapSize && maxHeap[left] > maxHeap[largest])
largest = left;
if (right < maxHeapSize && maxHeap[right] > maxHeap[largest])
largest = right;
if (largest != idx) {
swap(maxHeap[idx], maxHeap[largest]);
max_heapify(largest);
}
}
void insert_max_heap(int value) {
maxHeap[maxHeapSize] = value;
int current = maxHeapSize;
maxHeapSize++;
while (current > 0 && maxHeap[(current - 1) / 2] < maxHeap[current]) {
swap(maxHeap[current], maxHeap[(current - 1) / 2]);
current = (current - 1) / 2;
}
}
int extract_max() {
int root = maxHeap[0];
maxHeap[0] = maxHeap[--maxHeapSize];
max_heapify(0);
return root;
}
// Helper functions for Min Heap
void min_heapify(int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeapSize && minHeap[left] < minHeap[smallest])
smallest = left;
if (right < minHeapSize && minHeap[right] < minHeap[smallest])
smallest = right;
if (smallest != idx) {
swap(minHeap[idx], minHeap[smallest]);
min_heapify(smallest);
}
}
void insert_min_heap(int value) {
minHeap[minHeapSize] = value;
int current = minHeapSize;
minHeapSize++;
while (current > 0 && minHeap[(current - 1) / 2] > minHeap[current]) {
swap(minHeap[current], minHeap[(current - 1) / 2]);
current = (current - 1) / 2;
}
}
int extract_min() {
int root = minHeap[0];
minHeap[0] = minHeap[--minHeapSize];
min_heapify(0);
return root;
}
public:
MedianFinder() {
maxHeapSize = 0;
minHeapSize = 0;
}
void addNum(int num) {
if (maxHeapSize == 0 || num <= maxHeap[0]) {
insert_max_heap(num);
} else {
insert_min_heap(num);
}
// Balance the heaps
if (maxHeapSize > minHeapSize + 1) {
insert_min_heap(extract_max());
} else if (minHeapSize > maxHeapSize) {
insert_max_heap(extract_min());
}
}
double find_median() {
if (maxHeapSize == minHeapSize)
return (maxHeap[0] + minHeap[0]) / 2.0;
return maxHeap[0];
}
};
int main() {
MedianFinder mf;
// Simulate adding numbers to the data stream
int nums[] = {5, 2, 1, 3, 8, 7, 9};
int n = sizeof(nums) / sizeof(nums[0]);
for (int i = 0; i < n; i++) {
mf.addNum(nums[i]);
cout << "Median after adding " << nums[i] << ": " << mf.find_median() << endl;
}
return 0;
}
Output:
Day 21 showcased the versatility of heaps in solving real-world problems, especially those involving priority management and dynamic data streams. Through these exercises, I gained a deeper appreciation for heap operations and their critical role in efficient algorithm design and competitive programming. 🚀