Heap in Data Structures

A Heap is a specialized tree‑based data structure that satisfies the heap property. It is a complete binary tree that can be implemented as an array. Heaps are the foundation for Priority Queues and Heap Sort, two of the most important algorithms in computer science.

Heap Property

• Max‑Heap: For every node i other than the root, A[parent(i)] ≥ A[i]. The largest element is at the root.
• Min‑Heap: For every node i other than the root, A[parent(i)] ≤ A[i]. The smallest element is at the root.

Complete Binary Tree Property

A heap is a complete binary tree, meaning all levels are fully filled except possibly the last, which is filled from left to right. This property allows the heap to be efficiently represented as an array.

Array Representation of a Heap

For a node at index i (0‑based indexing):

• Parent: (i - 1) // 2
• Left Child: 2 * i + 1
• Right Child: 2 * i + 2

Index:     0    1    2    3    4    5    6
Array:   [ 50, 30, 40, 20, 10, 35, 25 ]

       50
      /  \
     30   40
    / \   / \
   20 10 35 25

Basic Operations

1. heapify (Sift Down / Sift Up)

Restores the heap property at a given node. Used after insertion or deletion.

• Sift Down (Max-Heap): If a node is smaller than its children, swap with the larger child and continue down.
• Sift Up (Max-Heap): If a node is larger than its parent, swap with the parent and continue up.

2. insert (Push)

Adds a new element at the end, then sifts it up to restore the heap property.

3. extractMax / extractMin

Removes and returns the root (max or min), replaces it with the last element, then sifts down to restore the heap property.

4. buildHeap

Converts an arbitrary array into a heap in O(n) time using the heapify operation on internal nodes.

5. peek

Returns the root element without removing it (max or min).

Implementation in Python

Max-Heap Implementation

class MaxHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def sift_up(self, i):
        while i > 0 and self.heap[i] > self.heap[self.parent(i)]:
            self.swap(i, self.parent(i))
            i = self.parent(i)

    def sift_down(self, i):
        n = len(self.heap)
        max_idx = i
        left = self.left_child(i)
        right = self.right_child(i)
        if left < n and self.heap[left] > self.heap[max_idx]:
            max_idx = left
        if right < n and self.heap[right] > self.heap[max_idx]:
            max_idx = right
        if max_idx != i:
            self.swap(i, max_idx)
            self.sift_down(max_idx)

    def insert(self, value):
        self.heap.append(value)
        self.sift_up(len(self.heap) - 1)

    def extract_max(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        max_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        if self.heap:
            self.sift_down(0)
        return max_val

    def peek(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        return self.heap[0]

    def size(self):
        return len(self.heap)

    def is_empty(self):
        return len(self.heap) == 0

    def build_heap(self, arr):
        self.heap = arr[:]
        n = len(self.heap)
        for i in range(n // 2 - 1, -1, -1):
            self.sift_down(i)

# Example usage
heap = MaxHeap()
heap.build_heap([10, 20, 15, 30, 40])
print(heap.heap)  # [40, 30, 15, 10, 20]
heap.insert(50)
print(heap.peek())  # 50
print(heap.extract_max())  # 50
print(heap.heap)  # [40, 30, 15, 10, 20]

Min-Heap Implementation

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def sift_up(self, i):
        while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
            self.swap(i, self.parent(i))
            i = self.parent(i)

    def sift_down(self, i):
        n = len(self.heap)
        min_idx = i
        left = self.left_child(i)
        right = self.right_child(i)
        if left < n and self.heap[left] < self.heap[min_idx]:
            min_idx = left
        if right < n and self.heap[right] < self.heap[min_idx]:
            min_idx = right
        if min_idx != i:
            self.swap(i, min_idx)
            self.sift_down(min_idx)

    def insert(self, value):
        self.heap.append(value)
        self.sift_up(len(self.heap) - 1)

    def extract_min(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        min_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        if self.heap:
            self.sift_down(0)
        return min_val

    def peek(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        return self.heap[0]

    def build_heap(self, arr):
        self.heap = arr[:]
        n = len(self.heap)
        for i in range(n // 2 - 1, -1, -1):
            self.sift_down(i)

Implementation in Java

import java.util.ArrayList;

class MaxHeap {
    private ArrayList heap;

    public MaxHeap() {
        heap = new ArrayList<>();
    }

    private int parent(int i) { return (i - 1) / 2; }
    private int leftChild(int i) { return 2 * i + 1; }
    private int rightChild(int i) { return 2 * i + 2; }

    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    private void siftUp(int i) {
        while (i > 0 && heap.get(i) > heap.get(parent(i))) {
            swap(i, parent(i));
            i = parent(i);
        }
    }

    private void siftDown(int i) {
        int n = heap.size();
        int maxIdx = i;
        int left = leftChild(i);
        int right = rightChild(i);
        if (left < n && heap.get(left) > heap.get(maxIdx)) maxIdx = left;
        if (right < n && heap.get(right) > heap.get(maxIdx)) maxIdx = right;
        if (maxIdx != i) {
            swap(i, maxIdx);
            siftDown(maxIdx);
        }
    }

    public void insert(int value) {
        heap.add(value);
        siftUp(heap.size() - 1);
    }

    public int extractMax() {
        if (heap.isEmpty()) throw new RuntimeException("Heap is empty");
        int maxVal = heap.get(0);
        heap.set(0, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) siftDown(0);
        return maxVal;
    }

    public int peek() {
        if (heap.isEmpty()) throw new RuntimeException("Heap is empty");
        return heap.get(0);
    }

    public int size() { return heap.size(); }
    public boolean isEmpty() { return heap.isEmpty(); }

    public void buildHeap(int[] arr) {
        heap.clear();
        for (int val : arr) heap.add(val);
        for (int i = heap.size() / 2 - 1; i >= 0; i--) siftDown(i);
    }
}

// Example usage
class Main {
    public static void main(String[] args) {
        MaxHeap heap = new MaxHeap();
        heap.buildHeap(new int[]{10, 20, 15, 30, 40});
        System.out.println(heap.peek());  // 40
        heap.insert(50);
        System.out.println(heap.extractMax());  // 50
    }
}

Using Java's PriorityQueue (Min-Heap)

import java.util.PriorityQueue;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        // Min-Heap (default)
        PriorityQueue minHeap = new PriorityQueue<>();
        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(5);
        System.out.println(minHeap.peek());  // 5

        // Max-Heap using reverse comparator
        PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(10);
        maxHeap.add(20);
        maxHeap.add(5);
        System.out.println(maxHeap.peek());  // 20
    }
}

Implementation in C++

#include 
#include 
#include 
using namespace std;

class MaxHeap {
private:
    vector heap;

    int parent(int i) { return (i - 1) / 2; }
    int leftChild(int i) { return 2 * i + 1; }
    int rightChild(int i) { return 2 * i + 2; }

    void siftUp(int i) {
        while (i > 0 && heap[i] > heap[parent(i)]) {
            swap(heap[i], heap[parent(i)]);
            i = parent(i);
        }
    }

    void siftDown(int i) {
        int n = heap.size();
        int maxIdx = i;
        int left = leftChild(i);
        int right = rightChild(i);
        if (left < n && heap[left] > heap[maxIdx]) maxIdx = left;
        if (right < n && heap[right] > heap[maxIdx]) maxIdx = right;
        if (maxIdx != i) {
            swap(heap[i], heap[maxIdx]);
            siftDown(maxIdx);
        }
    }

public:
    void insert(int value) {
        heap.push_back(value);
        siftUp(heap.size() - 1);
    }

    int extractMax() {
        if (heap.empty()) throw runtime_error("Heap is empty");
        int maxVal = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) siftDown(0);
        return maxVal;
    }

    int peek() {
        if (heap.empty()) throw runtime_error("Heap is empty");
        return heap[0];
    }

    int size() { return heap.size(); }
    bool isEmpty() { return heap.empty(); }

    void buildHeap(vector& arr) {
        heap = arr;
        for (int i = heap.size() / 2 - 1; i >= 0; i--) {
            siftDown(i);
        }
    }
};

// Example usage
int main() {
    MaxHeap heap;
    vector arr = {10, 20, 15, 30, 40};
    heap.buildHeap(arr);
    cout << heap.peek() << endl;  // 40
    heap.insert(50);
    cout << heap.extractMax() << endl;  // 50
    return 0;
}

Using C++ STL Priority Queue

#include 
#include 
using namespace std;

int main() {
    // Max-Heap (default)
    priority_queue maxHeap;
    maxHeap.push(10);
    maxHeap.push(20);
    maxHeap.push(5);
    cout << maxHeap.top() << endl;  // 20

    // Min-Heap using greater comparator
    priority_queue, greater> minHeap;
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);
    cout << minHeap.top() << endl;  // 5
    return 0;
}

Complexity Analysis

Heap Sort Algorithm

Heap Sort uses a heap to sort an array in O(n log n) time with O(1) extra space.

def heap_sort(arr):
    # Build max heap
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)

    # Extract max one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(arr, i, 0)

def sift_down(arr, n, i):
    max_idx = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[max_idx]:
        max_idx = left
    if right < n and arr[right] > arr[max_idx]:
        max_idx = right
    if max_idx != i:
        arr[i], arr[max_idx] = arr[max_idx], arr[i]
        sift_down(arr, n, max_idx)

arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print(arr)  # [5, 6, 7, 11, 12, 13]

Applications of Heaps

• Priority Queue: Used in task scheduling, Dijkstra's algorithm, and A* search.
• Heap Sort: An efficient, in‑place sorting algorithm with O(n log n) time.
• K‑th Largest/Smallest Element: Can find in O(n log k) time using a heap.
• Median Maintenance: Use two heaps to maintain the median of a stream.
• Graph Algorithms: Prim's and Dijkstra's algorithms use heaps for efficient extraction.
• Job Scheduling: Manage jobs by priority.
• Event Simulation: Process events in chronological order.

Advantages & Disadvantages

Advantages

• Efficient: O(log n) insert and extract operations.
• In‑place: Heap Sort uses O(1) extra space.
• Priority Access: Always gives quick access to max/min element.
• Simple Array Representation: No pointer overhead, cache‑friendly.

Disadvantages

• Limited Search: Searching for arbitrary elements is O(n).
• No Random Access: Cannot access elements by index efficiently.
• Not Flexible: Only supports extracting max/min, not arbitrary deletions.

Common Heap Problems

• Kth Largest Element: Find the k‑th largest element in an array.
• Top K Frequent Elements: Find the k most frequent elements.
• Merge K Sorted Lists: Use a min‑heap to merge k sorted lists efficiently.
• Sliding Window Maximum: Use a max‑heap (or deque) to find max in each window.
• Find Median in a Stream: Use two heaps (min and max).
• Minimum Cost to Connect Ropes: Always merge the two smallest ropes using a min‑heap.

Key Takeaways

• A heap is a complete binary tree that satisfies the heap property.
• Max‑Heap has the largest element at the root; Min‑Heap has the smallest.
• Heaps are efficiently represented as arrays with simple parent/child formulas.
• Operations: insert (O(log n)), extract (O(log n)), peek (O(1)), buildHeap (O(n)).
• Heaps power Priority Queues and Heap Sort.
• Heaps are essential for many graph algorithms and stream processing problems.