Before using the Heap sort method, we represent our array as a min heap. A min heap is a min tree that is also a complete binary tree. A min tree is a tree in which the value in each node is less or equal to those in its children (if any).

The heap sort then extracts elements from the heap one at a time by deleting the root of the heap, which is always the smallest element in the heap, and restructures the tree after that to have a min heap again with the smallest element as the root. The process continues until no more elements are left in the heap. The deleted elements are placed in the array, which will appear sorted at the end of heap sort.

Start the animation
Home Next algorithm