Understanding Heaps

What Is a Heap?

A heap is a special tree-based data structure used to maintain a collection of elements where quick access to the minimum or maximum element is required. Heaps are complete binary trees, meaning all levels are fully filled except possibly the last, and nodes are filled from left to right.

Heaps play an important role in implementing priority queues, memory management, scheduling algorithms, and Heap Sort.

Types of Heaps

1. Min Heap

• The value of each node is less than or equal to its children.

• The root always contains the smallest value.

       10
      /  \
    20    15
   /  \
  30  40

2. Max Heap

• The value of each node is greater than or equal to its children.

• The root always contains the largest value.

       50
      /  \
    30    40
   /  \
  20  10

Why Use Heaps?

Heaps allow efficient operations such as:

• Get Min/Max: O(1)

• Insert: O(log n)

• Delete Min/Max: O(log n)

They are faster than arrays, linked lists, and many other structures for priority-based operations.

Properties of Heaps

1. Complete Binary Tree: Always filled level by level.

2. Heap Order Property:

   • Min Heap ? parent <= child

   • Max Heap ? parent >= child

3. Stored in Arrays: Heaps are usually stored in arrays (not linked lists).

Array Representation

For a heap stored in an array:

• Parent of index i ? (i - 1) / 2

• Left child ? 2 * i + 1

• Right child ? 2 * i + 2

Example (Min Heap array):

[10, 20, 15, 30, 40]

Core Heap Operations

1. Insertion — O(log n)

Steps:

1. Insert element at the end

2. Perform heapify up (bubble up) to restore heap property

public void Insert(int value)
{
    heap.Add(value);
    int index = heap.Count - 1;

    while (index > 0)
    {
        int parent = (index - 1) / 2;
        if (heap[index] >= heap[parent]) break;

        (heap[index], heap[parent]) = (heap[parent], heap[index]);
        index = parent;
    }
}

2. Extract Min (or Max) — O(log n)

Steps:

1. Replace root with last element

2. Remove last element

3. Perform heapify down to restore heap property

public int ExtractMin()
{
    int min = heap[0];
    heap[0] = heap[^1];
    heap.RemoveAt(heap.Count - 1);

    HeapifyDown(0);
    return min;
}

3. Heapify Down

private void HeapifyDown(int index)
{
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < heap.Count && heap[left] < heap[smallest])
        smallest = left;

    if (right < heap.Count && heap[right] < heap[smallest])
        smallest = right;

    if (smallest != index)
    {
        (heap[index], heap[smallest]) = (heap[smallest], heap[index]);
        HeapifyDown(smallest);
    }
}

Priority Queue Using Heap

A priority queue removes the highest or lowest priority element first. It is implemented using heaps internally.

In C#:

PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
pq.Enqueue(10, 10);
pq.Enqueue(5, 5);
pq.Enqueue(20, 20);

Console.WriteLine(pq.Dequeue()); // 5

Applications of Heaps

Heaps are used in many high-performance systems:

1. Heap Sort

A popular sorting algorithm with:

• Time: O(n log n)

• Space: O(1)

2. Priority Queues

Used in:

• CPU scheduling

• Graph algorithms (Dijkstra, Prim)

• A* search in AI

3. Memory Management

Heaps store dynamically allocated memory blocks.

4. Order Statistics

Find kth smallest or largest element.

5. Real-Time Event Simulation

Events processed based on time priority.

Example: Heap Sort (Using Max Heap)

public void HeapSort(int[] arr)
{
    int n = arr.Length;

    for (int i = n / 2 - 1; i >= 0; i--)
        Heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--)
    {
        (arr[0], arr[i]) = (arr[i], arr[0]);
        Heapify(arr, i, 0);
    }
}

Time and Space Complexity

Space: O(n)

Summary

Heaps are powerful structures for managing priority-based data. They provide efficient insertion, deletion, and retrieval of minimum or maximum values.

Key takeaways:

• Complete binary tree

• Uses array representation

• Min heap returns the smallest value quickly

• Max heap returns the largest value quickly

• Widely used in priority queues, scheduling, and sorting