Heap / Priority Queue

Partially ordered complete tree that hands you the extreme element instantly.

Newinterview weight 7015 problems2 visualisers

mastery

Attempts logged

Predicted success on the next one

33%

Solved here

0 / 15

What you actually need to hold in your head

Array backed, children sit at 2i+1 and 2i+2
Top K with a heap of size K
Two heaps track a running median
Heapify builds in linear time

Comfortable with these first

This unlocks

Watch it run

Step through the algorithm before you write it.

Heap SortM

Build a max heap in place, then repeatedly swap the root to the end and sift the new root down.

O(n log n)

Heap: Push and PopM

A complete binary tree stored in an array. Push sifts the new value up, pop moves the last value to the root and sifts it down.

O(log n) per operation

Patterns in this topic

The trigger phrases are what you are training yourself to notice.

Top K with a HeapO(n log k)

Keep a heap of exactly K elements of the opposite polarity, so the worst survivor is always at the top and cheap to evict.

k largest or smallestk closest points

Two HeapsO(log n) per insert, O(1) query

Split the data into a max heap of the lower half and a min heap of the upper half, rebalancing so their sizes differ by at most one.

median of a streamsliding window median