19. Heaps / Priority Queues

🧸 ELI5: Imagine a hospital emergency room. It's not first-come-first-served — the person with the worst injury gets seen first, no matter when they arrived. A heap is a special box that always lets you grab the "most urgent" item instantly, and it reorganizes itself automatically whenever something new comes in.

🌍 Real life: Hospital triage. Task schedulers in your OS deciding which program gets the CPU next. "Top K" trending topics on Twitter. Dijkstra's algorithm (next!) uses a heap to always process the "closest" unexplored city next.

📝 Pseudocode:

heap = new MinHeap()
heap.insert(5)
heap.insert(1)
heap.insert(3)
heap.extractMin()   // returns 1, the smallest/most urgent

🐹 Go (using the standard library's container/heap):

package main

import (
	"container/heap"
	"fmt"
)

type PatientHeap []int // lower number = more urgent

func (h PatientHeap) Len() int            { return len(h) }
func (h PatientHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h PatientHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *PatientHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *PatientHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func main() {
	er := &PatientHeap{5, 1, 3}
	heap.Init(er)
	heap.Push(er, 0) // a critical patient just arrived!

	for er.Len() > 0 {
		fmt.Println("treating urgency level:", heap.Pop(er))
	}
	// treating urgency level: 0, 1, 3, 5
}

🇨 C — C has no container/heap to import, so this is what that package does internally: an array where index i's children live at 2i+1/2i+2, kept valid by "bubbling" a value up or down after every change:

#include <stdio.h>

#define HEAP_CAP 64

typedef struct { int items[HEAP_CAP]; int size; } MinHeap;

void heap_swap(MinHeap *h, int i, int j) {
    int t = h->items[i]; h->items[i] = h->items[j]; h->items[j] = t;
}

void heap_push(MinHeap *h, int value) {
    int i = h->size++;
    h->items[i] = value;
    while (i > 0) {                              // bubble up to restore the min-heap property
        int parent = (i - 1) / 2;
        if (h->items[parent] <= h->items[i]) break;
        heap_swap(h, parent, i);
        i = parent;
    }
}

int heap_pop(MinHeap *h) {
    int top = h->items[0];
    h->items[0] = h->items[--h->size];
    int i = 0;
    while (1) {                                    // bubble down to restore the min-heap property
        int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
        if (left < h->size && h->items[left] < h->items[smallest]) smallest = left;
        if (right < h->size && h->items[right] < h->items[smallest]) smallest = right;
        if (smallest == i) break;
        heap_swap(h, i, smallest);
        i = smallest;
    }
    return top;
}

int main(void) {
    MinHeap er = {0};
    heap_push(&er, 5);
    heap_push(&er, 1);
    heap_push(&er, 3);
    heap_push(&er, 0);  // a critical patient just arrived!

    while (er.size > 0) printf("treating urgency level: %d\n", heap_pop(&er));
    // treating urgency level: 0, 1, 3, 5
    return 0;
}

⏱️ Complexity: Insert / extract-min = O(log n). Peek at the top = O(1).