Heap Sort Algorithm

Heap Sort is a popular and efficient sorting algorithm in computer programming. Learning how to write the heap sort algorithm requires knowledge of two types of data structures - arrays and trees.

The initial set of numbers that we want to sort is stored in an array e.g. [10, 3, 76, 34, 23, 32] and after sorting, we get a sorted array [3,10,23,32,34,76]

Heap sort works by visualizing the elements of the array as a special kind of complete binary tree called heap.

What is a complete Binary Tree?

Binary Tree

A binary tree is a tree data structure in which each parent node can have at most two children

In the above image, each element has at most two children.

Full Binary Tree

A full Binary tree is a special type of binary tree in which every parent node has either two or no children.

Complete binary tree

A complete binary tree is just like a full binary tree, but with two major differences

1. Every level must be completely filled
2. All the leaf elements must lean towards the left.
3. The last leaf element might not have a right sibling i.e. a complete binary tree doesn’t have to be a full binary tree.

How to create a complete binary tree from an unsorted list (array)?

• Select first element of the list to be the root node. (First level - 1 element)
• Put the second element as a left child of the root node and the third element as a right child. (Second level - 2 elements)
• Put next two elements as children of left node of second level. Again, put the next two elements as children of right node of second level (3rd level - 4 elements).
• Keep repeating till you reach the last element.