Heaps & Priority Queues

// For node at index i:
private int Parent(int i) => (i - 1) / 2;   // Integer division
private int LeftChild(int i) => 2 * i + 1;
private int RightChild(int i) => 2 * i + 2;

// Example: Node at index 5
// Parent: (5-1)/2 = 2
// Left child: 2*5+1 = 11
// Right child: 2*5+2 = 12

        10 (idx 0)
       /  \
      20   30    (idx 1,2)
     / \  / \
    40 50 60 70 (idx 3,4,5,6)

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

For idx 1 (20):
  Parent: (1-1)/2 = 0 → 10 ✓
  Left:   2*1+1 = 3 → 40 ✓
  Right:  2*1+2 = 4 → 50 ✓

public void Insert(int value) {
    if (size == heap.Length) Resize();
    heap[size] = value;
    BubbleUp(size);
    size++;
}

private void BubbleUp(int idx) {
    while (idx > 0) {
        int parentIdx = Parent(idx);
        if (heap[parentIdx] <= heap[idx]) break; // Min-heap property satisfied
        Swap(idx, parentIdx);
        idx = parentIdx;
    }
}

public int ExtractMin() {
    if (size == 0) throw new InvalidOperationException("Heap empty");
    int min = heap[0];
    heap[0] = heap[--size];
    BubbleDown(0);
    return min;
}

private void BubbleDown(int idx) {
    while (LeftChild(idx) < size) {
        int smallest = idx;
        int left = LeftChild(idx);
        int right = RightChild(idx);

        if (heap[left] < heap[smallest]) smallest = left;
        if (right < size && heap[right] < heap[smallest]) smallest = right;
        if (smallest == idx) break; // Heap property satisfied

        Swap(idx, smallest);
        idx = smallest;
    }
}

public int Peek() {
    if (size == 0) throw new InvalidOperationException("Heap empty");
    return heap[0];
}

public static void BuildHeap(int[] arr) {
    int n = arr.Length;
    // Start from last non-leaf node: (n-2)/2
    for (int i = (n - 2) / 2; i >= 0; i--) {
        HeapifyDown(arr, i, n);
    }
}

private static void HeapifyDown(int[] arr, int idx, int n) {
    while (2 * idx + 1 < n) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        int smallest = idx;

        if (arr[left] < arr[smallest]) smallest = left;
        if (right < n && arr[right] < arr[smallest]) smallest = right;
        if (smallest == idx) break;

        (arr[idx], arr[smallest]) = (arr[smallest], arr[idx]);
        idx = smallest;
    }
}

Original:   [7, 4, 1, 9, 2, 5]
Tree:          7
             /   \
            4     1
           / \   /
          9   2 5

Start from i = (6-2)/2 = 2 (node with value 1)
  → Already min-heap at 1 since no valid children in tree position

i = 1 (node with value 4)
  → Left child = 9, Right = 2
  → Swap with 2 (smaller): [7, 2, 1, 9, 4, 5]
  → 4 now has no more children below

i = 0 (node with value 7)
  → Left = 2, Right = 1
  → Swap with 1 (smaller): [1, 2, 7, 9, 4, 5]
  → Move to position 2 (value 7)
  → Children are 4 and 5, swap with 4: [1, 2, 4, 9, 7, 5]

Result:     [1, 2, 4, 9, 7, 5] (valid min-heap)

public class MinHeap {
    private int[] heap;
    private int size;
    private const int DEFAULT_CAPACITY = 10;

    /// <summary>Initialize empty heap with default capacity</summary>
    public MinHeap() {
        heap = new int[DEFAULT_CAPACITY];
        size = 0;
    }

    /// <summary>Initialize with specific capacity</summary>
    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    /// <summary>Build heap from existing array - O(n)</summary>
    public MinHeap(int[] arr) {
        heap = new int[arr.Length];
        Array.Copy(arr, heap, arr.Length);
        size = arr.Length;
        BuildHeap();
    }

    // ===== Query Operations =====

    /// <summary>Get minimum without removing - O(1)</summary>
    public int Peek() {
        if (size == 0) throw new InvalidOperationException("Heap is empty");
        return heap[0];
    }

    /// <summary>Check if heap is empty</summary>
    public bool IsEmpty() => size == 0;

    /// <summary>Get current size</summary>
    public int Size() => size;

    // ===== Modification Operations =====

    /// <summary>Add element to heap - O(log n)</summary>
    public void Insert(int value) {
        if (size == heap.Length) {
            Resize();
        }
        heap[size] = value;
        BubbleUp(size);
        size++;
    }

    /// <summary>Remove and return minimum - O(log n)</summary>
    public int ExtractMin() {
        if (size == 0) throw new InvalidOperationException("Heap is empty");

        int min = heap[0];
        heap[0] = heap[--size];

        if (size > 0) {
            BubbleDown(0);
        }

        return min;
    }

    // ===== Internal Helper Methods =====

    /// <summary>Restore heap property from index upward</summary>
    private void BubbleUp(int idx) {
        while (idx > 0) {
            int parentIdx = Parent(idx);
            if (heap[parentIdx] <= heap[idx]) break;
            Swap(idx, parentIdx);
            idx = parentIdx;
        }
    }

    /// <summary>Restore heap property from index downward</summary>
    private void BubbleDown(int idx) {
        while (LeftChild(idx) < size) {
            int smallest = idx;
            int left = LeftChild(idx);
            int right = RightChild(idx);

            if (heap[left] < heap[smallest]) smallest = left;
            if (right < size && heap[right] < heap[smallest]) smallest = right;

            if (smallest == idx) break;

            Swap(idx, smallest);
            idx = smallest;
        }
    }

    /// <summary>Build heap from existing array - O(n)</summary>
    private void BuildHeap() {
        // Start from last non-leaf and work backwards
        for (int i = (size - 2) / 2; i >= 0; i--) {
            BubbleDown(i);
        }
    }

    /// <summary>Get parent index of element at position i</summary>
    private int Parent(int i) => (i - 1) / 2;

    /// <summary>Get left child index of element at position i</summary>
    private int LeftChild(int i) => 2 * i + 1;

    /// <summary>Get right child index of element at position i</summary>
    private int RightChild(int i) => 2 * i + 2;

    /// <summary>Swap elements at two indices</summary>
    private void Swap(int i, int j) {
        (heap[i], heap[j]) = (heap[j], heap[i]);
    }

    /// <summary>Double array capacity when full</summary>
    private void Resize() {
        int[] newHeap = new int[heap.Length * 2];
        Array.Copy(heap, newHeap, heap.Length);
        heap = newHeap;
    }

    /// <summary>Get array representation (for debugging)</summary>
    public int[] ToArray() {
        int[] result = new int[size];
        Array.Copy(heap, result, size);
        return result;
    }
}

// Create empty heap and insert
var heap = new MinHeap();
heap.Insert(5);
heap.Insert(3);
heap.Insert(7);
heap.Insert(1);

// Extract in sorted order
while (!heap.IsEmpty()) {
    Console.WriteLine(heap.ExtractMin()); // 1, 3, 5, 7
}

// Build heap from array - O(n)
int[] arr = { 7, 3, 9, 1 };
var heap2 = new MinHeap(arr);

public class MaxHeap {
    private int[] heap;
    private int size;

    public MaxHeap() => heap = new int[10];
    public MaxHeap(int[] arr) {
        heap = new int[arr.Length];
        Array.Copy(arr, heap, arr.Length);
        size = arr.Length;
        BuildHeap();
    }

    public int Peek() {
        if (size == 0) throw new InvalidOperationException("Heap empty");
        return heap[0];
    }

    public void Insert(int value) {
        if (size == heap.Length) Resize();
        heap[size] = value;
        BubbleUp(size);
        size++;
    }

    public int ExtractMax() {
        if (size == 0) throw new InvalidOperationException("Heap empty");
        int max = heap[0];
        heap[0] = heap[--size];
        if (size > 0) BubbleDown(0);
        return max;
    }

    // Only difference from MinHeap: > instead of < in comparisons
    private void BubbleUp(int idx) {
        while (idx > 0) {
            int parentIdx = (idx - 1) / 2;
            if (heap[parentIdx] >= heap[idx]) break; // Reverse for max
            Swap(idx, parentIdx);
            idx = parentIdx;
        }
    }

    private void BubbleDown(int idx) {
        while (2 * idx + 1 < size) {
            int largest = idx;
            int left = 2 * idx + 1;
            int right = 2 * idx + 2;

            if (heap[left] > heap[largest]) largest = left;
            if (right < size && heap[right] > heap[largest]) largest = right;

            if (largest == idx) break;
            Swap(idx, largest);
            idx = largest;
        }
    }

    private void BuildHeap() {
        for (int i = (size - 2) / 2; i >= 0; i--)
            BubbleDown(i);
    }

    private void Swap(int i, int j) =>
        (heap[i], heap[j]) = (heap[j], heap[i]);

    private void Resize() {
        int[] newHeap = new int[heap.Length * 2];
        Array.Copy(heap, newHeap, heap.Length);
        heap = newHeap;
    }

    public bool IsEmpty() => size == 0;
    public int Size() => size;
}

using System.Collections.Generic;

// Min-heap by default (lower priority value = higher priority)
var pq = new PriorityQueue<string, int>();

// Enqueue: Add element with priority
pq.Enqueue("task-high", 1);    // Priority 1
pq.Enqueue("task-low", 5);     // Priority 5
pq.Enqueue("task-med", 3);     // Priority 3

// Dequeue: Remove and return highest-priority element
while (pq.Count > 0) {
    string task = pq.Dequeue();
    Console.WriteLine(task);
}
// Output: task-high, task-med, task-low (ascending priority)

// Peek without removing
var (element, priority) = pq.Peek();

// Try operations (safe, return bool)
if (pq.TryDequeue(out string elem, out int pri)) {
    Console.WriteLine($"Got: {elem} (priority: {pri})");
}

// Get count
int remaining = pq.Count;

// EnqueueRange: Add multiple elements at once
var items = new[] {
    ("a", 1),
    ("b", 2)
};
pq.EnqueueRange(items);

// Option 1: Negate values
var maxHeap = new PriorityQueue<int, int>();
maxHeap.Enqueue(5, -5);   // Negate for max-heap
maxHeap.Enqueue(3, -3);
Console.WriteLine(maxHeap.Dequeue()); // 5

// Option 2: Custom comparer
var reverseComparer = new ReverseComparer<int>();
var maxHeap2 = new PriorityQueue<int, int>(reverseComparer);
maxHeap2.Enqueue(5, 5);
maxHeap2.Enqueue(3, 3);
Console.WriteLine(maxHeap2.Dequeue()); // 5

// Simple reverse comparer
public class ReverseComparer<T> : IComparer<T> where T : IComparable<T> {
    public int Compare(T a, T b) => b.CompareTo(a);
}

public record Task(string Name, int Priority, long Timestamp);
public record TaskPriority(int Priority, long Timestamp)
    : IComparable<TaskPriority> {
    public int CompareTo(TaskPriority other) {
        // Higher priority first
        int pri = other.Priority.CompareTo(this.Priority);
        if (pri != 0) return pri;
        // Then earlier timestamp (FIFO for same priority)
        return this.Timestamp.CompareTo(other.Timestamp);
    }
}

var pq = new PriorityQueue<Task, TaskPriority>();
pq.Enqueue(new Task("A", 1, 100), new TaskPriority(1, 100));
pq.Enqueue(new Task("B", 1, 50), new TaskPriority(1, 50));

public static void HeapSort(int[] arr) {
    int n = arr.Length;
    
    // Step 1: Build max-heap - O(n)
    for (int i = (n - 2) / 2; i >= 0; i--) {
        HeapifyDown(arr, i, n);
    }
    
    // Step 2: Extract max n-1 times - O(n log n)
    for (int i = n - 1; i > 0; i--) {
        // Move current max (root) to end
        (arr[0], arr[i]) = (arr[i], arr[0]);
        // Restore heap property in reduced array
        HeapifyDown(arr, 0, i);
    }
}

private static void HeapifyDown(int[] arr, int i, int n) {
    while (2 * i + 1 < n) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest == i) break;

        (arr[i], arr[largest]) = (arr[largest], arr[i]);
        i = largest;
    }
}

      

        
C#
        
// Example: Sort [3, 1, 4, 1, 5, 9, 2]
int[] arr = { 3, 1, 4, 1, 5, 9, 2 };
HeapSort(arr);
// Result: [1, 1, 2, 3, 4, 5, 9]
      

      
Complexity Analysis
      

        

          
Operation
Best
Average
Worst
Space
          

            
Heap Sort
O(n log n)
O(n log n)
O(n log n)
O(1)
            
Build Heap
O(n)
O(n)
O(n)
O(1)
            
Extract Max n times
O(n log n)
O(n log n)
O(n log n)
O(1)
          
        
      

      

        ⚠️
        
Not Stable: Heap sort doesn't preserve relative order of equal elements (unstable). Example: [1a, 2, 1b] may become [1b, 1a, 2]. For stable sort, use merge sort.
      
    

public static List<int> TopKLargest(int[] nums, int k) {
    // Min-heap: smallest of K largest elements at root
    var minHeap = new PriorityQueue<int, int>();
    
    foreach (int num in nums) {
        minHeap.Enqueue(num, num);
        
        // Keep heap size at most K
        if (minHeap.Count > k) {
            minHeap.Dequeue();
        }
    }
    
    var result = new List<int>();
    while (minHeap.Count > 0) {
        result.Add(minHeap.Dequeue());
    }
    result.Reverse(); // Reverse to get descending order
    return result;
}

// Example
int[] nums = { 3, 2, 1, 5, 6, 4 };
var topK = TopKLargest(nums, 2);
// Result: [6, 5]

public static List<int> TopKSmallest(int[] nums, int k) {
    // Max-heap: largest of K smallest elements at root
    var maxHeap = new PriorityQueue<int, int>(
        new ReverseComparer<int>());
    
    foreach (int num in nums) {
        maxHeap.Enqueue(num, num);
        
        // Keep heap size at most K
        if (maxHeap.Count > k) {
            maxHeap.Dequeue();
        }
    }
    
    var result = new List<int>();
    while (maxHeap.Count > 0) {
        result.Add(maxHeap.Dequeue());
    }
    result.Reverse(); // Reverse to get ascending order
    return result;
}
    

public class MedianFinder {
    private PriorityQueue<int, int> maxHeap; // Left half
    private PriorityQueue<int, int> minHeap; // Right half

    public MedianFinder() {
        maxHeap = new PriorityQueue<int, int>(
            new ReverseComparer<int>());
        minHeap = new PriorityQueue<int, int>();
    }

    public void AddNum(int num) {
        // Add to max-heap first
        if (maxHeap.Count == 0 || num <= maxHeap.Peek()) {
            maxHeap.Enqueue(num, num);
        } else {
            minHeap.Enqueue(num, num);
        }

        // Balance heaps: maxHeap can have at most 1 more element
        if (maxHeap.Count > minHeap.Count + 1) {
            minHeap.Enqueue(maxHeap.Dequeue(), 
                maxHeap.Peek());
        }
        if (minHeap.Count > maxHeap.Count) {
            maxHeap.Enqueue(minHeap.Dequeue(), 
                minHeap.Peek());
        }
    }

    public double FindMedian() {
        int total = maxHeap.Count + minHeap.Count;
        
        if (total % 2 == 1) {
            // Odd: return max of left half
            return maxHeap.Peek();
        } else {
            // Even: return average of both roots
            return (maxHeap.Peek() + minHeap.Peek()) / 2.0;
        }
    }
}

// Example
var mf = new MedianFinder();
mf.AddNum(1);
Console.WriteLine(mf.FindMedian()); // 1.0
mf.AddNum(2);
Console.WriteLine(mf.FindMedian()); // 1.5
mf.AddNum(3);
Console.WriteLine(mf.FindMedian()); // 2.0

public static List<int> MergeKSortedLists(List<List<int>> lists) {
    var result = new List<int>();
    
    // Min-heap: (value, listIndex, elementIndex)
    var minHeap = new PriorityQueue<(int val, int li, int ei), int>();
    
    // Add first element from each list
    for (int i = 0; i < lists.Count; i++) {
        if (lists[i].Count > 0) {
            minHeap.Enqueue((lists[i][0], i, 0), lists[i][0]);
        }
    }
    
    // Extract min, add next from same list
    while (minHeap.Count > 0) {
        var (val, li, ei) = minHeap.Dequeue();
        result.Add(val);
        
        // Add next element from same list
        if (ei + 1 < lists[li].Count) {
            int nextVal = lists[li][ei + 1];
            minHeap.Enqueue((nextVal, li, ei + 1), nextVal);
        }
    }
    
    return result;
}

// Example: Merge [[1,4,5], [1,3,4], [2,6]]
var lists = new List<List<int>> {
    new() { 1, 4, 5 },
    new() { 1, 3, 4 },
    new() { 2, 6 }
};
var merged = MergeKSortedLists(lists);
// Result: [1, 1, 2, 3, 4, 4, 5, 6]