Skip to content

Heap [mp]

Micro pattern

Description

Maintain efficient access to the highest- or lowest-priority active candidate.

Problems

Heap implementation

Represent a complete binary tree in an array and restore its order by sifting.

Maintain the best k values

Keep a size-\(k\) heap whose root is the weakest retained candidate.

K-way merge

Keep one current smallest item from each sorted source.

Balanced halves

Maintain one heap for each half of an ordered data stream.

Active sweep candidates

Prioritize active candidates as sweep coordinates advance.

Heap-based sorting

Move the root into the sorted suffix and restore the reduced heap.