A binary heap is an array-based complete binary tree that satisfies the heap property:

  • Min-heap: every parent is <= its children. The minimum is at the root.
  • Max-heap: every parent is >= its children. The maximum is at the root.

It's the standard way to implement a priority queue.

Array layout

Index 0 is the root. For node at index i:

  • left child = 2*i + 1
  • right child = 2*i + 2
  • parent = (i - 1) / 2
index   0   1   2   3   4   5
value   1   3   2   7   5   4

         1
        / \
       3   2
      / \  /
     7  5 4

Operations and their complexity

Op Time What it does
Push (insert) O(log n) Place at end, sift up.
Pop (extract) O(log n) Swap root with last, shrink, sift down.
Peek O(1) Return root.
Heapify O(n) Build a heap from an unordered slice (sift down).
Update O(log n) Change a value, then sift up or down.

What we implement

heapx.MinHeap[T constraints.Ordered] — a generic min-heap with:

  • Push(v T), Pop(), Peek(), Len(), Heapify(s []T).
  • A free function IsMinHeap(s []T) bool to check the heap property.
  • A KSmallest(s []T, k int) []T example application that returns the k smallest elements of s in O(n log k) time using a max-heap (we build the max-heap by negating the comparison via a flipped wrapper — see the test).

Comparison with container/heap

The standard library has container/heap which provides the algorithm against an interface you implement. It's flexible but verbose. We build our own for clarity. (We do use container/heap once in Chapter 8 for Dijkstra to demonstrate the standard pattern.)

Run the tests

go test ./part2-dsa/ds/heapx