Dec 30, 2019
Heap sort and it’s working process
Heap sort
Heap sort is one of the best and efficient sorting methods in computer programming and was invented by J. W. J. Williams in 1964. Heap sort involves building a Heap data structure from the given array and then utilizing the Heap to sort the array. To understand this, let's find out what is a Heap.
Heap is a special treebased data structure, that satisfies special heap properties, like 
Shape Property  Heap data structure is always a Complete Binary Tree, which means all levels of the tree are fully filled.
Heap Property  All nodes are either greater than or less than or equal to each of its children. Greater parent nodes heap is called a MaxHeap and small parent nodes heap is called MinHeap.
How heap sort works?
Heap sort algorithm is divided into two basic parts 

A heap is built out of the data. The heap is often placed in an array with the layout of a complete binary tree.

Once heap is built, the first element of the Heap is either largest or smallest, so put the first element of the heap in an array.

The complete binary tree maps the binary tree structure into the array indices; each array index represents a node; the index of the node's parent, left child branch, or right child branch is simple expressions. [Example  For a zerobased array, the root node is stored at index 0; if i is the index of the current node, then parent(i) = floor((i1) / 2) where floor functions map a real number to the smallest leading integer. leftChild(i) = 2*i + 1, rightChild(i) = 2*i + 2]

Then a sorted array is created by repeatedly removing the largest element from the heap (the root of the heap), and inserting it into the array.

Again make heap using the remaining elements, to pick again the first element of the heap and put it into the array.

Keep on doing the same repeatedly until you have the complete sorted list in your array.

The heap is updated after each removal to maintain the heap property.

Once all objects have been removed from the heap, the result is a sorted array.
Logic of Heap Sort
# heapify
for i = n/2:1, sink(a,i,n)
invariant: a[1,n] in heap order
# sortdown
for i = 1:n,
swap a[1,ni+1]
sink(a,1,ni)
invariant: a[ni+1,n] in final position
end
# sink from i in a[1..n]
function sink(a,i,n):
# {lc,rc,mc} = {left,right,max} child index
lc = 2*i
if lc > n, return # no children
rc = lc + 1
mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
if a[i] >= a[mc], return # heap ordered
swap a[i,mc]
sink(a,mc,n)
return result
Performance

Worst Case Time Complexity: O(n log n)

Best Case Time Complexity: O(n)

Average Time Complexity: O(n log n)

Space Complexity: O(1)