Heaps & Priority Queues

A heap keeps the smallest (or largest) element of a changing collection one read away. It is an array read as a complete binary tree where every parent beats its children and nothing else is ordered, so a push or a pop only touches one root-to-leaf path.

	C++	Python	Java
Type	priority_queue	heapq	PriorityQueue
Default order	largest first	smallest first	smallest first

A heap only shows you its top element. It cannot look up or delete an arbitrary value in the middle, so removing specific elements requires lazy deletion, where you record the value as deleted in a map or set and discard it once it rises to the top. To track the $k$ largest values in a stream, keep a min-heap of size $k$ and evict its top whenever a bigger value arrives, since the smallest survivor is the threshold to beat.

Operation	Heap	Sorted array
Peek at the extreme	$O(1)$	$O(1)$
Insert or pop the extreme	$O(\log n)$	$O(n)$
Build from $n$ values	$O(n)$	$O(n \log n)$

Reach for one when a problem wants the current extreme again and again while the collection keeps changing, such as tracking the top $k$ of a stream, merging sorted lists one cursor at a time, or revising the worst earlier choice in a greedy pass.

The problems below start with repeated extremes and a size-$k$ heap, move through $k$-way merge cursors and greedy passes that trade or combine the smallest choices, and end with two heaps maintaining a sliding median under lazy deletion.