Heap Sort in C++
Heap Sort Program in C++
Heap Sort technique is based of binary tree. Heap Sort is very fast data sorting technique and it is widely used for sorting. Heap sort algorithm is divided into two basic parts
- Creating a Heap of the unsorted list.
- Then a sorted array is created by repeatedly removing the largest/smallest element from the heap, and inserting it into the array. The heap is reconstructed after each removal.
What is heap
Heap is a special tree-based data structure. Heap sort is based on binary tree concept. Binary tree have mainly two property
- Shape Property
- Heap Property
Shape Property
Heap sort data structure is always a Complete Binary Tree. In case of Complete binary tree all levels of the tree are fully filled.
Shape Property
In binary tree value of each node is either (greater than or equal to) or (less than or equal to) of the parent node. If the parent or father nodes are greater than their children node then this type of heap is called a Max-Heap, and if the parent nodes are smaller than their child nodes then this type of heap is called Min-Heap.
Heap Sort Working
First receive un-sorted list and create a Heap data structure(Max-Heap or Min-Heap). Now you can put the first element of the heap in your array ( the first element of the Heap is either largest or smallest(depending upon Max-Heap or Min-Heap)). Again make heap using remaining list data. pick first element and put this into array. This process is repeated until list complete sorted.