Heap sort and it’s working process

Geekboots ⚭ Programming ⚭ Dec 29, 2019 ⚭ 117 views

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)

Heap Sort Implementation in different Programming Languages

Sort your data using Heap Sort in Python

Sort your data using Heap Sort in Java

Sort your data using Heap Sort in C

Sort your data using Heap Sort in C++