Heaps introduction

Heaps

A heap is a tree-shaped structure that keeps the smallest (or largest) element instantly available. A min-heap guarantees that every parent is <= its children, so the minimum is always at the root. (A max-heap flips the comparison.)

Stored as an array

Heaps are usually a complete binary tree packed into an array — no pointers needed. For the node at index i:

parent: (i-1)/2
left child: 2*i + 1
right child: 2*i + 2

The root (the min) sits at index 0.

The two operations

Insert (sift-up): append the value at the end, then swap it upward while it's smaller than its parent — until the heap property holds again.

Extract-min (sift-down): the root is the answer; move the last element to the root, then swap it downward with its smaller child until it settles.

Both touch at most one root-to-leaf path, so they're O(log n). Peeking the min is O(1).

When to use one

A priority queue — unlike a plain queue (first-in-first-out), a priority queue always dequeues the highest- (or lowest-) priority item next, whatever order things arrived. A heap is the usual way to implement one: peek the min in O(1), extract in O(log n).
"Top k" / "kth largest" — a size-k heap keeps the running best in O(n log k).
Merging sorted streams, Dijkstra's shortest paths, scheduling.

Go ships container/heap, but you'll hand-roll sift-up and sift-down here to see the array index math up close. Once you have those two helpers, everything else is built on top.