A min-heap is a priority queue whose smallest-priority element appears at the top. It returns lower-priority values first, while preserving the remaining ordering as an implementation detail rather than a fully sorted list. section 2.5.4 section 2.8.3
Use a min-heap when repeatedly selecting the smallest current priority:
- Store compound values such as (priority, task) tuples and rely on their natural ordering. section 2.5.4
- For the k largest elements, keep a min-heap bounded to k entries; compare each new value with the smallest retained value, replacing it when larger. section 2.7.2
- Convert a max-heap design into a min-heap design by negating priorities, or exchange the comparison directions symmetrically. section 2.5.4
Huffman coding
Count character frequencies, insert one tree node per character into a min-heap, then repeatedly extract the two lowest-frequency nodes. Merge them into a new node whose frequency is their sum, reinsert it, and continue until one tree remains. The heap supplies the least frequent subtrees in the required order. section 2.8.3
