⛁ Binary Heap

A binary heap is a complete binary tree kept in a plain array, where every parent beats its children (a min-heap: parent ≤ both children). That single rule makes insert and extract-min O(log n) and gives you a priority queue. Watch new values bubble up and the root sift down — in the tree and the array at once.

★ Star on GitHub

Empty heap. Insert a value — it lands at the end, then bubbles up to its spot.

size

height

min (root)

—

valid heap?

yes

Try this: insert a few values and watch each one bubble up — it starts at the end of the array and swaps with its parent while it's smaller, so the smallest reaches the root. Then extract-min: the root (the answer) is removed, the last element moves to the top, and it sifts down, swapping with its smaller child until the heap rule holds again. The array is the tree — for index i, its parent is ⌊(i−1)/2⌋ and children are 2i+1 and 2i+2, so no pointers are needed. heapify random builds a valid heap from a shuffled array in O(n) (sift down from the last parent up) — faster than inserting one-by-one. This is exactly the priority queue behind Dijkstra, Prim, Huffman coding, and heapsort.