# 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 tree-based 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 Max-Heap and small parent nodes heap is called Min-Heap.

## 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 zero-based array, the root node is stored at index 0; if i is the index of the current node, then parent(i) = floor((i-1) / 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,n-i+1]
sink(a,1,n-i)
invariant: a[n-i+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)