Click to hide these details

This is a basic visualization of Max Heap data structure (ADT Priority Queue).
Upon loading this web page, a quick animation of a scripted Max Heap {90,19,36,17,3,25,1,2,7} (9 entries) will be shown.
The entries will be shown layer by layer, left to right, to illustrate the "Complete Binary Tree" structure.

Limitation(s):
1). Due to screen size, this visualization is limited to 31 entries in the Max Heap (or 5 layers/levels of Complete Binary Tree).
2). This visualization uses Max Heap property.
If Min Heap is needed, one can simply workaround this issue by negating the input numbers.
You can copy paste this: {-90,-19,-36,-17,-3,-25,-1,-2,-7} to textbox "A" and click buildV1() or buildV2(), then ignore the '-' sign.

There are eight actions that you can do in this visualization:

1. Reset;
Re-show the same quick animation of a scripted Max Heap as after page load.

2. Insert(v);
Type in a new two-digits (or just use existing) number in the text box "v", then click Insert(v).
PS: We randomize the value of "v" at every click of Insert(v).
First, a new vertex will appear as the bottom-most, right-most new leaf, then the Max Heap property is checked.
Vertex highlighted with this magenta color is the current vertex.
Vertex highlighted with this green color is the smaller parent of the current vertex that violates Max Heap property with the current vertex.
The magenta vertex and the green vertex will be swapped (shiftUp) in the next iteration.

3. ExtractMax();
First, the root and the last vertex will be swapped, then the Max Heap property is checked.
Vertex highlighted with this magenta color is the current vertex.
Vertex highlighted with this green color is the larger child of the current vertex that violates Max Heap property with the current vertex.
The magenta vertex and the green vertex will be swapped (shiftDown) in the next iteration.

4. heapSort();
This animation shows successive calls of ExtractMax() (quick version) until the Max Heap is empty.
Vertex highlighted with this magenta color is the next vertex to be inserted into the sorted list (descending order).
Vertices highlighted with this green color are the affected vertices after the previous call of ExtractMax().
Once heapSort() animation stops, only button Reset(), buildV1(), buildV2() will be available.

5. buildV1();
This animation shows successive calls of Insert(v) (quick version) starting from an empty Max Heap.
These values are taken from the text box "A".
This version runs in O(n log n).
Copy paste this worst possible input to text box "A" to see buildV1() does the most work:
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31}.
Vertex highlighted with this magenta color is the vertex that has just been recently inserted into Max Heap.
Vertices highlighted with this green color are the affected vertices after the previous call of Insert(v), if any.

6. buildV2();
This animation shows a better way to build a Max Heap from an array "A".
We start by just dumping the entire array "A" into a complete binary tree.
Then, starting from the last internal node back to the root (half of the size of "A"), we call shiftDown to fix Max Heap property.
This version runs in O(n), try it on the worst possible input shown in buildV1() above.
Vertex highlighted with this magenta color is the root of the sub-tree that is currently examined for Max Heap property violation, if any.
Vertices highlighted with this green color are the affected vertices after the previous call of shiftDown(), if any.

7. Slower (<<);
Make the animation two times slower.

8. Faster (>>);
Make the animation two times faster.