minheap

A min-heap, or minimum heap, is a complete binary tree data structure that maintains the heap property: the key at each node is less than or equal to the keys of its children. The smallest key is always at the root, making access to the minimum element straightforward. Binary min-heaps are the most common form, but heaps with higher arity (d-ary heaps) are also used in some implementations.

In practice, a min-heap is typically stored as an array. For a node at index i, the left child is at 2i+1, the right child at 2i+2, and the parent at floor((i-1)/2). The array representation allows efficient, cache-friendly access and simple in-place updates.

Core operations include insert, which adds the new element at the end and then bubbles it up (sift up) until the heap property holds; extract-min, which removes the root and replaces it with the last element, then sifts down (heapifies) to restore the property; and decrease-key, which lowers the value of a key and may bubble it up. The minimum element can be retrieved in O(1) time with a peek at the root. Building a heap from an unsorted array can be done in O(n) time using a bottom-up heapify process.

Time complexities: insert, extract-min, and decrease-key run in O(log n) time for a binary min-heap; find-min is O(1). Memory usage is O(n).

Min-heaps are widely used to implement priority queues, in algorithms such as Dijkstra’s shortest path and Prim’s minimum spanning tree. They also underpin Huffman coding trees. Heaps are not stable with equal keys, unless stability is explicitly enforced, and they do not support efficient arbitrary key search. Compared to a max-heap, a min-heap keeps the smallest element at the root.