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. No lookup by value, no delete by value, no second smallest without popping the first, so anything that removes arbitrary elements needs lazy deletion — mark the value gone and drop it once it surfaces. The size-k trick is worth memorising too. For the k largest values keep a min-heap of size k and evict its top, since the smallest survivor is the one guarding the door.

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 data underneath keeps moving — the top k of a stream, sorted lists merged a cursor at a time, or a greedy that refunds its cheapest earlier commitment.

The problems below start with repeated extremes and the size-k bouncer, move through k-way merge cursors and greedies that refund or merge the two smallest, and end with two heaps facing each other under lazy deletion.