Binary Heap In C++

Introduction:

Binary heap serves as a crucial data structure frequently employed in the field of computer science to effectively manage priority queues. This structure is characterized by being a complete binary tree, ensuring that every node contains a value that is either less than or equal to its child nodes in the case of a min-heap, or greater in a max-heap scenario.

Binary Heap:

A binary heap is typically represented as an array, where the parent-child relationships are defined based on the indices of the array elements. In a binary heap, for any node at index i:

• ✅ Its left child is at index 2*i + 1.
• ✅ Its right child is at index 2*i + 2.
• ✅ Its parent is at index (i - 1) / 2.

There exist two variations of binary heaps: min-heap and max-heap.

Within a min-heap, every node's value is either less than or equal to the values of its children.

Conversely, in a max-heap, each node's value is greater than or equal to the values of its children.

The primary characteristic of a binary heap is the heap order property, guaranteeing that the top node (at position 0) holds the smallest (or largest) value in a min-heap (or max-heap, correspondingly).

Construction:

A binary heap is commonly shown as an array, with the children of the node at index i positioned at indices 2i+1 and 2i+2. This array-based representation enables effective handling and organization of the heap data structure. Take a look at this illustration:

In array format, the identical heap would be shown as: [5, 9, 11, 14, 18, 19, 21].

Operations on Binary Heap:

• ✅ Insertion: When a new element is added to the heap, it is placed at the bottom, maintaining the complete binary tree property. Then, it is "bubbled up" or "percolated up" to its correct position by comparing it with its parent and swapping if necessary.
• ✅ Deletion: Removal of the root element from the heap. After removal, the last element in the array takes the root's place. Then, it is "bubbled down" or "percolated down" to its correct position by comparing it with its children and swapping if necessary.
• ✅ Heapify: This operation builds a heap from a given array. It starts from the last non-leaf node and performs the "bubble down" operation until all nodes satisfy the heap property.
• ✅ Extract Max/Min: This operation removes and returns the maximum (for max heap) or minimum (for min heap) element from the heap. It involves removing the root element and rearranging the heap to maintain its properties.

Implementation:

#include <iostream>
#include <vector>
using namespace std;
class MinHeap {
private:
    vector<int> heap;
    // Helper function to heapify the subtree rooted at index i
    void heapify(int i) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < heap.size() && heap[left] < heap[smallest])
            smallest = left;
        if (right < heap.size() && heap[right] < heap[smallest])
            smallest = right;
        if (smallest != i) {
            swap(heap[i], heap[smallest]);
            heapify(smallest);
        }
    }
public:
    // Constructor
    MinHeap() {}
    // Function to insert a new element into the heap
    void insert(int value) {
        heap.push_back(value);
        int i = heap.size() - 1;
        while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
            swap(heap[i], heap[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }
    // Function to extract the minimum element from the heap
    int extractMin() {
        if (heap.empty())
            return -1; // or throw an exception
        int root = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        heapify(0);
        return root;
    }
};
int main() {
    MinHeap minHeap;
    minHeap.insert(12);
    minHeap.insert(7);
    minHeap.insert(6);
    minHeap.insert(10);
    minHeap.insert(8);
    cout << "Minimum element: " << minHeap.extractMin() << endl;
    return 0;
}

Explanation:

• ✅ The program defines a class MinHeap to encapsulate the heap operations.
• ✅ In the MinHeap class, there is a private member heap which is a vector storing the elements of the heap.
• ✅ The heapify function is a helper function used to maintain the min-heap property. It takes an index i as input and recursively adjusts the subtree rooted at index i to ensure it satisfies the min-heap property.
• ✅ The insert function inserts a new element into the heap. It first adds the element to the end of the vector and then performs a "bubble-up" operation to move the element up the tree until its parent is smaller than or equal to it, ensuring the min-heap property is maintained.
• ✅ The extractMin function removes and returns the minimum element from the heap. It first checks if the heap is empty, returning -1 if so (this could alternatively throw an exception).
• ✅ It then replaces the root (minimum element) with the last element in the vector, removes the last element, and calls heapify on the root to restore the min-heap property.
• ✅ In the main function, an instance of MinHeap is created, and several elements are inserted into it using the insert function. Then, the minimum element is extracted from the heap using extractMin and printed to the console.

Program Output:

Time Complexity Analysis:

• ✅ Insertion (insert): Inserting an element into a binary heap involves adding it at the end of the heap array and then performing the heapifyUp operation, which has a time complexity of O(log n), where n is the number of elements in the heap. Therefore, the overall time complexity for insertion is O(log n).
• ✅ Extraction (extractMin): Extracting the minimum element from a min-heap requires removing the root node and replacing it with the last element of the heap array. This is followed by the heapifyDown operation, which has a time complexity of O(log n), where n is the number of elements in the heap. Hence, the overall time complexity for extraction is O(log n).
• ✅ Accessing Minimum Element: Accessing the minimum element in a min-heap is a constant-time operation, as the minimum element is always stored at the root node. Therefore, the time complexity for accessing the minimum element is O(1).

Application of Binary Heaps:

Binary heaps find applications in various algorithms and data structures due to their efficient nature:

• ✅ Priority Queues: Binary heaps are commonly used to implement priority queues, where elements are inserted with an associated priority and retrieved in order of priority.
• ✅ Heap Sort: Heap sort is a comparison-based sorting algorithm that uses binary heaps to sort elements in ascending (or descending) order efficiently.
• ✅ Dijkstra's Algorithm: This algorithm for finding the shortest paths between nodes in a graph uses a priority queue, often implemented using a binary heap, to efficiently select the next node to explore.

Advantages:

• ✅ Simple Representation: Binary Heaps can be efficiently represented using arrays, resulting in reduced overhead compared to tree-based representations.
• ✅ Efficient Operations: Insertion, deletion, and retrieval of the maximum or minimum element can be performed in logarithmic time complexity.

Conclusion:

In summary, the binary heap data structure in C++ offers an effective method for managing a priority queue, enabling rapid retrieval of the topmost (or bottommost) priority item. Due to its well-balanced tree organization and heap characteristics, binary heaps deliver logarithmic time efficiency for adding and removing elements, rendering them ideal for various scenarios requiring swift access to ordered data.

By integrating functions for adding, removing, and restructuring heaps, programmers can leverage binary heaps to enhance algorithms and boost efficiency in different software endeavors. A crucial component in the realm of computer science and coding, understanding and applying binary heap concepts in C++ provides a pathway to elegantly and effectively tackle intricate challenges.