HeapsData structureaka max priority queue, maximum heap

Max-Heap

A complete binary tree in array form where every parent is ≥ its children, so the maximum is always at the root.

▶ Visualize Pattern: Heap / Priority Queue Practice (4)

Progress

Definition

A max-heap is the mirror image of a Min-Heap: the invariant is parent ≥ child, so a[0] is the largest element. Every algorithm is identical with the comparison flipped.

It is the natural structure when the "best" element is the largest: Heap Sort builds a max-heap and repeatedly moves the root to the end of the array; a size-k max-heap tracks the k smallest items; the lower half of a running-median pair is a max-heap.

In practice you rarely write a separate class. Either the library heap takes a comparator (C++, Java, Go), or you negate keys (Python heapq with -x) to turn a min-heap into a max-heap.

priority queuecomplete binary treearray-backedO(log n)heap sort

Intuition

A mental model before the formal terms.

Same tournament bracket as the min-heap, but the match winner is the *larger* number. The champion at the top is the maximum; removing it re-runs only the matches on one path down the bracket.

Heap sort is just "pull the champion, put them at the end of the array, shrink the bracket, repeat" — after n rounds the array is sorted ascending.

How it works

Array layout as in Binary Heap: parent (i-1)/2, children 2i+1, 2i+2.
Insert: append, then sift up while the element is greater than its parent.
Extract-max: swap root with last, shrink, sift the root down toward the larger child while a child is greater.
Heapify from an array in O(n) by sifting down indices n/2 - 1 … 0.
Increase-key is the mirror of decrease-key: raise the value and sift up.
To get a max-heap from a min-heap library: negate numeric keys, or supply a reversed comparator.

Why it works

The argument for Min-Heap holds with ≤ replaced by ≥: a local invariant at each parent implies the root dominates every node via induction on the path from the root.

Sift operations preserve completeness (only the last slot is added/removed) and restore the ordering along a single path of length ⌊log₂ n⌋.

Operations

Operation	Description	Cost
peek / top	Return the maximum at index 0.	O(1)
push	Append and sift up while larger than the parent.	O(log n)
pop / extract-max	Move last to root and sift down toward the larger child.	O(log n)
heapify	Bottom-up construction from an unordered array.	O(n)
increase-key	Raise a key at a known index and sift up.	O(log n)
search	Linear scan; no cross-sibling ordering.	O(n)

Recognition

How to tell a problem wants this.

The problem asks for the largest (most frequent, highest priority, furthest) element repeatedly from a changing set.
"K closest / k smallest" — keep a max-heap of size k and evict the root whenever it is beaten.
In-place O(n log n) sort with O(1) extra memory → Heap Sort on a max-heap.
A running median needs a max-heap for the lower half.

“k most frequent” → Heap / Priority Queue “maximum number of non-overlapping” → Greedy

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Binary Heap visualization.

Commands — "insert N" or "extract", separated by commas

Empty tree

Heap array (level order)

empty

1/45Empty min-heap. Invariant: every parent ≤ its children, and the tree is complete, so it can live in an array with parent(i) = (i−1)/2.

Newly insertedElement being siftedCompared withSwappedExtracted minimum

PseudocodeLearn Binary Heap →

1insert(x): append x at the end; i = n-1
2  while i > 0 and heap[i] < heap[parent(i)]: swap; i = parent(i)   # sift up
3extract(): min = heap[0]; move last element to the root; n -= 1
4  i = 0; while smallest child < heap[i]: swap with the smaller child; continue   # sift down
5parent(i) = (i-1)//2, children = 2i+1, 2i+2

Variables

Complexity

access O(1)

search O(n)

insert O(1)

delete O(log n)

Speed

Pseudocode

1push(x): a.append(x); sift_up(last) while a[parent] < a[i]
2pop(): top = a[0]; a[0] = a.pop_last(); sift_down(0) toward larger child
3heap_sort(a):
4  build max-heap
5  for end = n-1 down to 1: swap(a[0], a[end]); sift_down(0, limit=end)

Implementation

1import heapq
2 
3 
4class MaxHeap:
5    """Max-heap on top of heapq (a MIN-heap) by negating numeric keys."""
6 
71 · Storage and construction
8    def __init__(self, items=None):
9        self._a = [-x for x in items] if items is not None else []
10        heapq.heapify(self._a)  # O(n)
11 
122 · Push
13    def push(self, x) -> None:
14        heapq.heappush(self._a, -x)  # store the negation
15 
163 · Pop (extract-max)
17    def pop(self):
18        return -heapq.heappop(self._a)  # negate back on the way out
19 
204 · Peek and size
21    def peek(self):
22        return -self._a[0]
23 
24    def __len__(self) -> int:
25        return len(self._a)
26 
27    def __bool__(self) -> bool:
28        return bool(self._a)

Walkthrough

heapq only does min-heaps, so every key is stored negated: push -x, peek/pop return -a[0].
__init__ negates the initial items before the O(n) heapify.
The negation is confined to this class; callers see a normal max-heap API.
This is the representative Python idiom — for non-numeric keys use tuples (-priority, counter, payload) instead.

Complexity (this implementation)

time O(log n) push/pop, O(1) peek, O(n) heapify · space O(n)

Language notes

Negation works for ints/floats; for strings or objects negate an explicit numeric key or wrap items in a class with reversed __lt__.
Python ints are arbitrary precision, so -x never overflows — the same trick in C++ can overflow INT_MIN.
heapq.nlargest(k, xs) covers many one-shot max-side queries without building a heap yourself.

Common mistakes in this language

Negating on push but forgetting to negate on pop or peek.
Negating tuples with non-numeric fields (-("a",) is a TypeError).
Mixing negated and raw values in the same list.

Language differences that matter here

Defaults invert across languages: C++ std::priority_queue is max-heap by default, Python heapq is min-only (negate keys for max), JS/TS have neither and hand-roll both.
Python fakes a max-heap by storing negated keys; C++/TS/JS flip the comparator instead — negation breaks for non-numeric keys.
C++ negation of INT_MIN is undefined behavior; Python negation is always safe (arbitrary-precision ints); JS is safe within ±2^53.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Maximum only.
Search	O(n)	O(n)
Insert	O(1)	O(log n)
Delete	O(log n)	O(log n)
Update	O(log n)	O(log n)	Increase-key from a known index.
Peek	O(1)	O(1)
Extract-max	O(log n)	O(log n)
Heapify	O(n)	O(n)
Space	O(n)

Advantages & disadvantages

Advantages

Identical performance profile to the min-heap: O(1) max, O(log n) push/pop, O(n) build.
Enables in-place Heap Sort with O(1) extra space.
Available for free by flipping the comparator or negating keys.

Disadvantages

Only the maximum is accessible; no ordered iteration or fast search.
Negating keys in Python is error-prone with tuples and non-numeric payloads.
Not stable for equal keys without an explicit tiebreaker.

Use cases

Heap Sort: build a max-heap, swap root to the end, shrink, sift down.
K smallest / k closest points: size-k max-heap, discard the root when a smaller item arrives.
Running median: max-heap of the lower half paired with a min-heap of the upper half.
Task scheduler: repeatedly pick the task with the highest remaining count.
Stock / bid matching: highest bid at the top of the buy-side book.

Use it when

Repeatedly need the largest element of a changing collection.
K smallest elements with bounded memory.
In-place sorting with guaranteed O(n log n) and O(1) extra space.

Avoid it when

You need ordered iteration or range queries — use a Binary Search Tree or sort once.
Maximum of a sliding window — a Monotonic Queue does it in amortised O(1) per step.
Only a single max is needed — a linear scan is simpler and faster.

Alternatives

Min-Heap Priority Queue Monotonic Queue Binary Search Tree

Common mistakes

Negating keys but forgetting to negate on the way out.
Assuming std::priority_queue is a min-heap (it is a max-heap by default).
Sift-down comparing against the smaller child instead of the larger one.
Off-by-one in heap sort: the sift-down limit must exclude the already-placed suffix.

Interview patterns

K closest points to origin: size-k max-heap keyed on distance.
Last stone weight: pop two largest, push the difference.
Find median from a data stream with a max-heap / min-heap pair.
Reorganize string / task scheduler: always pick the most frequent remaining item.

Interview questions on this

Where does O(n log n) come from?Beginner
Top K from a streamIntermediate
When a hash map is the wrong choiceIntermediate
Greedy or dynamic programming?Advanced

Mock interviews

Kth Largest Element in an ArrayIntermediate
Network Delay TimeAdvanced
Merge IntervalsIntermediate

Interview problems

Kth Largest Element in an Arraymedium Top K Frequent Elementsmedium Find Median from Data Streamhard Task Schedulermedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related