A Heap is a specialized tree-based data structure that satisfies the Heap Property. Heaps are commonly used to implement priority queues and ensure efficient retrieval of the minimum or maximum element.

Video Explanation​

Watch

Introduction​

A Heap is a complete binary tree, which means every level is fully filled except possibly the last level, which is filled from left to right. The heap is used to efficiently manage a priority queue, allowing us to retrieve the highest or lowest priority element in constant time.

Heaps can be represented as arrays, which helps in reducing the space complexity by avoiding pointers.

Types of Heaps​

Max Heap​

In a Max Heap, for every node i, the value of i is greater than or equal to the values of its children. Therefore, the root of the tree contains the maximum element.

       50
      /  \
    30    20
   /  \   / 
 15   10  8

Min Heap​

In a Min Heap, for every node i, the value of i is less than or equal to the values of its children. The root contains the minimum element.

       10
      /  \
     15   30
    /  \   / 
   50   20  40

Heap Operations​

Insert​

Inserting an element in a heap involves adding the new element at the end of the tree (or array representation) and then "bubbling up" to restore the heap property.

1. Insert the element at the next available position.
2. Compare the element with its parent and swap if necessary (heapify up).

Delete​

The element to be deleted is usually the root (for priority queues). The last element of the heap replaces the root, and the heap property is restored by "bubbling down" (heapify down).

1. Replace the root with the last element.
2. Restore the heap property by moving the element down (heapify down).

Peek​

The peek operation returns the root element of the heap without removing it:

• For a Max Heap, this returns the maximum element.
• For a Min Heap, this returns the minimum element.

Heapify​

Heapifying ensures that a subtree satisfies the heap property. Two types of heapify operations are:

• Heapify Up: Used in insertion.
• Heapify Down: Used in deletion.

Applications​

• Priority Queue: Used in scheduling processes, graph algorithms (like Dijkstra's shortest path).
• Heap Sort: Sorting algorithm using heaps.
• Graph Algorithms: Like Prim's and Dijkstra's shortest path algorithms.
• Median Maintenance: Heaps can be used to keep track of the median in a dynamic dataset.

Time Complexity​

• Insertion: $O(log n)$
• Deletion: $O(log n)$
• Peek: $O(1)$
• Heapify: $O(log n)$

Implementation​

C++ Code Example​

Here’s a C++ implementation of a Max Heap:

#include <iostream>
#include <vector>

using namespace std;

class MaxHeap {
    vector<int> heap;

    // Heapify up to restore the heap property after insertion
    void heapifyUp(int index) {
        if (index == 0) return;
        int parentIndex = (index - 1) / 2;
        if (heap[parentIndex] < heap[index]) {
            swap(heap[parentIndex], heap[index]);
            heapifyUp(parentIndex);
        }
    }

    // Heapify down to restore the heap property after deletion
    void heapifyDown(int index) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int largest = index;

        if (leftChild < heap.size() && heap[leftChild] > heap[largest]) {
            largest = leftChild;
        }

        if (rightChild < heap.size() && heap[rightChild] > heap[largest]) {
            largest = rightChild;
        }

        if (largest != index) {
            swap(heap[index], heap[largest]);
            heapifyDown(largest);
        }
    }

public:
    // Insert a new element into the heap
    void insert(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    // Remove the maximum element from the heap
    void removeMax() {
        if (heap.size() == 0) return;
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
    }

    // Peek the maximum element (root)
    int getMax() {
        if (heap.size() == 0) throw runtime_error("Heap is empty");
        return heap[0];
    }

    // Print heap elements
    void printHeap() {
        for (int val : heap) {
            cout << val << " ";
        }
        cout << endl;
    }
};

int main() {
    MaxHeap maxHeap;

    maxHeap.insert(50);
    maxHeap.insert(30);
    maxHeap.insert(20);
    maxHeap.insert(15);
    maxHeap.insert(10);
    maxHeap.insert(8);

    cout << "Heap after insertions: ";
    maxHeap.printHeap();

    cout << "Max element: " << maxHeap.getMax() << endl;

    maxHeap.removeMax();
    cout << "Heap after removing max: ";
    maxHeap.printHeap();

    return 0;
}

Complexity Cheat Sheet​