Heaps in C++

What is Heap?

Heaps are complete binary trees, meaning all levels are fully filled except possibly the last level, which is filled from left to right.

Types:

Max-Heap:

Heap in which parent's data is greater than children's data. Moreover, left and right subtree should also be max-heap.

Min-Heap:

Heap in which parent's data is less than children's data. Moreover, left and right subtree should also be min-heap.

Heap Operations:

1. Insert

To insert a new element into a heap, follow these steps:

1. Add the element to the end of the heap.
2. Heapify-up to maintain the heap property.

2. Delete (Extract Max/Min)

To remove the root element (max or min) from a heap, follow these steps:

1. Replace the root with the last element.
2. Remove the last element.
3. Heapify-down to maintain the heap property.

Heapify:

Heapify is the process of converting a binary tree into a heap. There are two types of heapify operations:

Heapify-up: Used in insertion to maintain the heap property by moving the inserted element up the tree.

To maintain the max-heap property when adding a new element, follow these steps:

1. Compare the current node with its parent.

2. If the current node is larger than its parent, swap them.

3. Repeat the process for the parent node until the heap property is restored or the root is reached.

Heapify-down: Used in deletion to maintain the heap property by moving the root element down the tree.

To maintain the max-heap property, follow these steps:

1. Compare the current node with its children.

2. If the current node is smaller than its largest child, swap them.

3. Repeat the process for the child node until the heap property is restored.

Heap Using Array

Heaps are commonly implemented using arrays. For a node at index `i`:

• The parent node is at index: (i - 1) / 2.
• The left child is at index: 2 * i + 1.
• The right child is at index: 2 * i + 2.

Example: Max-Heap Using Array

Here is an example of how to implement a max-heap using an array in C++:

#include <iostream>
using namespace std;

// Class to represent a Max Heap
class MaxHeap {
private:
    int* h;        // Array to store heap elements
    int maxSize;   // Maximum possible size of the heap
    int currSize;  // Current number of elements in the heap

    // Function to maintain the max-heap property by moving the node at index up
    void up_Heap(int Index) {
        if (Index == 0)  // If the node is the root, return
            return;
        else {
            int Parent = (Index - 1) / 2;  // Calculate the parent index

            if (h[Parent] < h[Index]) {  // If the parent is smaller than the current node
                swap(h[Parent], h[Index]);  // Swap the parent and the current node
                up_Heap(Parent);  // Recursively call up_Heap on the parent
            }
        }
    }

    // Function to maintain the max-heap property by moving the node at index down
    void down_Heap(int Index) {
        int Largest = Index;  // Assume the current node is the largest
        int Left_Child = 2 * Index + 1;  // Calculate the left child index
        int Right_Child = 2 * Index + 2;  // Calculate the right child index

        // If the left child exists and is greater than the current node
        if (Left_Child < currSize && h[Left_Child] > h[Largest])
            Largest = Left_Child;
        // If the right child exists and is greater than the largest so far
        if (Right_Child < currSize && h[Right_Child] > h[Largest])
            Largest = Right_Child;

        // If the largest is not the current node, swap and continue heapifying down
        if (Largest != Index) {
            swap(h[Largest], h[Index]);
            down_Heap(Largest);
        }
    }

    // Function to remove and return the maximum element (root) of the heap
    void removeMax(int& Value) {
        if (currSize == 0)  // If the heap is empty, print message and return
        {
            cout << "Heap is Empty!" << endl;
            return;
        }

        Value = h[0];  // The root is the maximum element
        h[0] = h[currSize - 1];  // Move the last element to the root
        currSize--;  // Decrease the size of the heap
        down_Heap(0);  // Heapify down from the root
    }

public:
    // Constructor to initialize the heap with a given maximum size
    MaxHeap(int Size) {
        maxSize = Size;
        h = new int[maxSize];  // Allocate memory for the heap array
        currSize = 0;  // Initialize current size to 0
    }

    // Function to build the heap from an array
    void buildHeap(int* arr, int size) {
        for (int i = 0; i < size; i++)  // Insert all elements into the heap
        {
            insertSingleValue(arr[i]);
        }
    }

    // Function to insert a single value into the heap
    void insertSingleValue(int Value) {
        if (currSize == maxSize)  // If the heap is full, print message and return
        {
            cout << "Heap is Full!" << endl;
            return;
        }

        h[currSize] = Value;  // Insert the new value at the end of the heap
        up_Heap(currSize);  // Heapify up from the last element
        currSize++;  // Increase the size of the heap
    }

    // Function to print the elements of the heap
    void printHeap() {
        if (currSize == 0)  // If the heap is empty, print message and return
        {
            cout << "Heap is Empty!" << endl;
            return;
        }

        for (int i = 0; i < currSize; i++)  // Print all elements in the heap
        {
            cout << h[i] << " ";
        }
        cout << endl;
    }

    // Function to extract and return the maximum element (root) of the heap
    int extractMax() {
        if (currSize == 0)  // If the heap is empty, print message and return -1
        {
            cout << "Heap is Empty!" << endl;
            return -1;
        }

        int maxVal = h[0];  // The root is the maximum element
        h[0] = h[currSize - 1];  // Move the last element to the root
        currSize--;  // Decrease the size of the heap
        down_Heap(0);  // Heapify down from the root
        return maxVal;  // Return the maximum element
    }
};

// Main function to demonstrate the functionality of the MaxHeap class
int main() {
    MaxHeap heap(10);  // Create a max heap with a maximum size of 10

    // Insert elements into the heap
    heap.insertSingleValue(10);
    heap.insertSingleValue(20);
    heap.insertSingleValue(30);
    heap.insertSingleValue(5);
    heap.insertSingleValue(7);
    heap.insertSingleValue(40);
    heap.insertSingleValue(15);

    // Print the heap elements
    cout << "Heap elements: ";
    heap.printHeap();
    // Output: 40 20 30 5 7 10 15

    // Extract the maximum element from the heap
    cout << "Extracted max: " << heap.extractMax() << endl;
    // Output: Extracted max: 40

    // Print the heap elements after extraction
    cout << "Heap elements after extraction: ";
    heap.printHeap();
    // Output: 30 20 15 5 7 10

    // Extract the maximum element again
    cout << "Extracted max: " << heap.extractMax() << endl;
    // Output: Extracted max: 30

    // Print the heap elements after extraction
    cout << "Heap elements after second extraction: ";
    heap.printHeap();
    // Output: 20 10 15 5 7

    return 0;
}