Heap

For “Heap”, identify the priority and whether work arrives as a stream. A heap is appropriate when you repeatedly need the next best item, not merely a one-time sort. Use a min-heap to keep the largest k values by evicting the smallest when size exceeds k; use a max-heap when repeatedly extracting the current maximum. In graph or scheduling variants, store enough metadata to detect stale entries and tie-break deterministically. State the invariant precisely: the root is always the least or greatest live candidate according to the comparator. Do not confuse a heap with fully sorted order; only the root is globally ordered. Test k equal to zero or input length, duplicate priorities, negative values, and ties. Building can be O(n), while each insertion or removal is O(log k) or O(log n), depending on the bounded size.