Max Heap Visualizer

A max heap is a complete binary tree where every parent node is greater than or equal to its children. The root always holds the maximum element, making it ideal for any problem that repeatedly needs the largest value.

Like all binary heaps, a max heap is stored as a flat array. For any node at index i:

• •Parent: floor((i - 1) / 2)
• •Left child: 2i + 1
• •Right child: 2i + 2

The max heap property guarantees that the largest element is always accessible in O(1) at the root, while insertion and extraction both run in O(log n).

Insert (sift up)

A new element is appended to the end of the array (maintaining the complete tree shape). Then it sifts up: compared with its parent and swapped if it's larger, climbing until it finds a parent that's greater or it reaches the root. At most log n swaps.

Extract Max (sift down)

The root (the maximum) is removed. The last element in the array takes its place at the root, then sifts down: compared with its children and swapped with the larger child until the max heap property is restored. This takes O(log n).

Heapsort with a Max Heap

Heapsort builds a max heap from the input array in O(n), then repeatedly extracts the maximum and places it at the end of the array. After n extractions, the array is sorted in ascending order. Total time: O(n log n), in-place, but not stable.

Use a max heap whenever you need fast access to the largest element:

• •Priority queues — Serve the highest-priority item first. OS task schedulers use max heaps to run the most important process next.
• •Heapsort — Build a max heap, then extract-max repeatedly. O(n log n) worst case, in-place, no extra memory.
• •Kth smallest element — Maintain a max heap of size K. If a new element is smaller than the root, pop and push. The root is the Kth smallest.
• •Median maintenance — Pair a max heap (lower half) with a min heap (upper half). The max heap root is the lower median.
• •Bandwidth/resource allocation — Always assign resources to the highest-demand request first.

The structure and algorithms are identical. The only difference is the comparison operator: a max heap uses >= and a min heap uses <=. You can convert between them by negating all values or flipping the comparator.

A max heap needs just an array and two core operations:

Sift Up (for insertion)

Starting from the inserted node, compare with the parent. If the node is larger, swap them and repeat from the parent's position. Stop when the node is smaller than its parent or becomes the root.

Sift Down (for extraction)

Starting from the root, compare with both children. Swap with the larger child (this is the key difference from min heap, where you swap with the smaller child). Repeat until the node is larger than both children or reaches a leaf.

Language-specific notes

Python: The heapq module only supports min heaps. The standard trick is to negate values: heapq.heappush(h, -val) and -heapq.heappop(h).

Java: Use new PriorityQueue<>(Collections.reverseOrder()).

C++: std::priority_queue is a max heap by default.

Max heaps show up in coding interviews more often than you'd expect:

• •Kth smallest element — Keep a max heap of size K. For each new element, if it's smaller than the root, pop and push. The root is the Kth smallest.
• •Median of a data stream — Use a max heap for the lower half and a min heap for the upper half. The max heap root gives the lower median.
• •Sort a nearly sorted array — Each element is at most K positions from its sorted position. Use a max heap (or min heap) of size K+1 to sort in O(n log K).
• •Merge K sorted arrays (descending) — Push the first element of each array into a max heap. Pop the largest, push the next from that array.
• •Task scheduler (LeetCode 621) — Use a max heap to always pick the task with the highest remaining count, respecting cooldown intervals.
• •Reorganize string (LeetCode 767) — Max heap of character frequencies. Pop the top two, append them alternately, push back with decremented counts.