04 Try it yourself Interactive

The tree and the array, moving together

Both pictures below are the same numbers, however many you load. The indigo ring is the value being moved right now; amber is the parent or child it is being compared against; rose means those two are swapping this step; green means that value has found its place. Watch the array row on every swap — one level of movement in the tree is always two cells trading places, and the index moves by i → (i-1)/2 going up, i → 2i+1 or 2i+2 going down. Switch to the second tab to empty the heap again.

Insert · sift up
i → (i-1)/2
2–7 whole numbers (0–99), commas or spaces.
the heap as a complete binary tree
the same heap as one flat array · index under each cell
Press Next to begin. Each press moves one step.


      

        
Heap size–

        
At index–

        
Comparisons0

        
Swaps0

      


      

      

        
        
        
        step 0 / 0