Heap Sort:

Before starting the heap sort we need to know the Tree Binary Data Structure very well.

Binary Tree Data Structure:

Binary Tree DS has one parent node and at least two child node (left and right).

We can classify Binary tree into three types,

1. Full Binary Tree
2. Complete Binary Tree
3. Almost Binary Tree.

let see one by one now,

Rules applicable for Binary Tree:

• We can move towards next level only when filling the current node value.
• We can fill the right node value only when filling the left node value

Full Binary Tree:

Every Node should have 2 child node apart from leaf nodes.

Complete Binary Tree:

There is no restriction of child node(In FBT we should have 2 child node at leaf nodes). We may have one or two nodes at leaf nodes.

Almost Complete Binary Tree:

Always leaf node should have one child.

Properties of Binary Tree

• number of levels = 0 to n
• number of nodes = 2^k - 1
• number of levels -> k = log (n + 1)
• number of leaf nodes (n/2) - Upper bound
• number of non - leaf nodes (n/2) - Lower bound

Now we will see implementation of Heap sort,

Heap Sort Implementation:

Heap sort uses the CBT and array data structure ( To save the space)

There are two type of heap sort one is min heap and another one is max heap,

Min Heap:

Parent node value should always lesser than the child node values.

Max heap:

Parent node value should always greater than the child node values.

Application:

It used to find max or min values.