Heap Data Structure Implementation

Heaps are specialized tree-based data structures that satisfy the heap property. They are commonly used to implement priority queues and for efficient sorting algorithms. This article explores two practical applications of heaps: heap sort and sequence merging.

Heap Sort Implemantation

Heap sort is an efficient comparison-based sorting algorithm that leverages the heap data structure. The algorithm works by first building a max heap from the input data and then repeaetdly extracting the maximum element and placing it at the end of the array.

The key to implementing heap sort is the heapify function, which maintains the heap property. Here's an implementation in C++:

#include <iostream>
#include <algorithm>
#define MAX_SIZE 100005
using namespace std;

int dataCount;
int heapArray[MAX_SIZE];

// Function to maintain heap property
void heapify(int startIdx, int endIdx) {
    int parent = startIdx;
    int child = 2 * parent; // Left child
    
    while (child <= endIdx) {
        // Check if right child exists and is greater
        if (child + 1 <= endIdx && heapArray[child + 1] > heapArray[child]) {
            child++;
        }
        
        // If child is greater than parent, swap them
        if (heapArray[child] > heapArray[parent]) {
            swap(heapArray[parent], heapArray[child]);
            parent = child;
            child = 2 * parent;
        } else {
            break;
        }
    }
}

// Function to build a max heap
void buildMaxHeap() {
    for (int i = dataCount / 2; i >= 1; i--) {
        heapify(i, dataCount);
    }
}

// Main heap sort function
void performHeapSort() {
    buildMaxHeap();
    for (int i = dataCount; i > 1; i--) {
        swap(heapArray[1], heapArray[i]);
        heapify(1, i - 1);
    }
}

int main() {
    cin >> dataCount;
    for (int i = 1; i <= dataCount; i++) {
        cin >> heapArray[i];
    }

    performHeapSort();
    for (int i = 1; i <= dataCount; i++) {
        cout << heapArray[i] << " ";
    }
    cout << endl;
    return 0;
}

Sequence Merging Using Priority Queues

Another interesting application of heaps is in merging sequences efficiently. Given two arrays, we want to find the n smallest sums of elements from these arrays. A naive approach would generate all possible sums, but this leads to O(n²) time complexity, which is inefficient for large arrays.

A more efficient approach uses a priority queue (min-heap) to keep track of the smallest sums without generating all possibilities. Here's a time-efficient implementation:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAX_VAL = 100002;

struct SumNode {
    int idx;      // Index in the first array
    int sumVal;   // Sum value
    
    // Overload the less than operator for priority queue
    bool operator<(const SumNode& other) const {
        return sumVal > other.sumVal; // For min-heap
    }
};

int main() {
    int n;
    int firstArr[MAX_VAL], secondArr[MAX_VAL];
    
    while (cin >> n) {
        // Read first array
        for (int i = 0; i < n; i++) {
            cin >> firstArr[i];
        }
        
        // Read second array
        for (int i = 0; i < n; i++) {
            cin >> secondArr[i];
        }
        
        // Priority queue to store sum nodes
        priority_queue<SumNode> minHeap;
        SumNode tempNode;
        
        // Initialize the heap with sums of each element in second array
        // with the first element of the first array
        for (int i = 0; i < n; i++) {
            tempNode.idx = 0;
            tempNode.sumVal = secondArr[i] + firstArr[0];
            minHeap.push(tempNode);
        }
        
        // Extract the n smallest sums
        for (int i = 0; i < n; i++) {
            SumNode current = minHeap.top();
            minHeap.pop();
            
            // If there are more elements in the first array,
            // add the next combination to the heap
            if (current.idx + 1 < n) {
                tempNode.idx = current.idx + 1;
                tempNode.sumVal = current.sumVal - firstArr[current.idx] + firstArr[tempNode.idx];
                minHeap.push(tempNode);
            }
            
            // Print the current smallest sum
            cout << current.sumVal << (i == n - 1 ? '\n' : ' ');
        }
    }
    
    return 0;
}

This implementation efficiently finds the n smallest sums by only considering necessary combinations, reducing the time complexity significantly compared to the brute-force approach.