Heap Sort

Heapsort is a comparison based sorting algorithm and is part of the selection sort family. It improves upon selection sort by implementing a logarithmic time priority queue and has an O(n log(n)) time complexity class for all cases.

1. We have an array, so we need to build a heap with it

Our array that we want to sort is this one : 7, 3, 2, 8, 1, 6.

We must have a heap in order to perform a heap sort.

First, we make a tree from the elements as shown, starting from the first and just placing them into a binary tree. The next step is to "heapify" the tree to make it a binary heap.
We can "bubble down" the elements into their correct positions to satisfy a min-heap. We want a min-heap to sort into ascending order, if we used a max-heap then the root would be the highest value and the next step would result in an array sorted in descending order.

2. We can now build a sorted array

We take the root of the heap each time and place it into the array. The array will be sorted as the root will be the smallet value in the heap.
Each time the root is removed, we replace it with the next highest priority node by bubbling down.
Take the next root and put that into the array and repeat...

The resulting array will be sorted : 1,2,3,6,7,8

Learn Computer Science

Developing a more interesting World

Free beginner - intermediate level computer science tutorials

Heap sort

1. We have an array, so we need to build a heap with it

2. We can now build a sorted array