Module 5 · Heaps · Heap Tree Implementation

Sort an array

Add every number to a min heap — each one sifts up past bigger parents — then poll the root again and again. The root is always the smallest left, so the polls come out sorted.

In the min heap every parent is smaller than its children. arr is the same heap as an array: the children of i are 2i+1 and 2i+2, and dimmed slots are outside the heap. allElement is what pollAll() returns.