Heap (Priority Queue)
Software Engineer path · lesson 17 of 99A specialized tree-based data structure which is essentially a complete binary tree that satisfies the heap property. In a max heap, for any given node I, the value of I is greater than or equal to the values of its children.
Syntax: push n · pop. Numbers from -99 to 99.
Empty heap
Empty max-heap. Stored as an array: children of i are at 2i+1 and 2i+2.
- 1push(x): a.append(x); i = last
- 2 while i > 0 and a[i] beats a[parent(i)]: swap them; i = parent(i) # sift up
- 3pop(): top = a[0]; a[0] = a.pop()
- 4 while a child beats a[i]: swap with the better child # sift down
- 5 return top # "beats" = smaller in a min-heap, larger in a max-heap
- Comparisons
- 0 / 12
- Swaps
- 0 / 6
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
What does it cost?
Sort each binary-heap operation by its time complexity.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
O(1)
Drop items hereO(log n)
Drop items hereO(n)
Drop items hereTest your knowledge
Where is the maximum element always located in a Max Heap?
The short version
Think of an emergency room triage. Patients are not treated in order of arrival (FIFO), but by severity. The most critical case (highest priority) is always handled next, regardless of wait time.
In more depth
The Priority Struct
A Heap is a specialized Tree-based data structure that satisfies the Heap Property. It is the most efficient way to repeatedly access the Highest or Lowest priority element.
Array Representation:
Heaps are typically implemented as arrays!
When to reach for this
- Find the **Top K** elements
- Find the **Median** of a stream
- Schedule tasks by Priority
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required