Heapsort was invented by John William Joseph Williams (J. W. J. Williams) in the year 1964.
Heap sort is a comparison-based sorting technique based on Binary Heap data structure called Heap Tree. It is similar to the selection sort where we first find the minimum element and place the minimum element at the beginning. Repeat the same process for the remaining elements. In this sorting algorithm, we use Max Heap to arrange list of elements in Ascending order and Min Heap to arrange list elements in Descending order.
The binary heap data structure is heap implementation that can be viewed as a complete binary tree built out of a given set of data. The heap data structure is also used in the construction of a priority queue.
A Max Heap is a complete binary tree such that for every node, key(parent) > key(child)
A Min Heap is a complete binary tree such that for every node, key(parent) < key (child)
function heapSort(arr):
n = length(arr)
// Build a max heap from the array
for i from n / 2 - 1 to 0:
heapify(arr, n, i)
// Extract elements one by one from the heap
for i from n - 1 to 0:
// Move current root to end
swap arr[0] with arr[i]
// Call max heapify on the reduced heap
heapify(arr, i, 0)
// To heapify a subtree rooted with node i, which is an index in arr[]
function heapify(arr, n, i):
largest = i // Initialize largest as root
left = 2 * i + 1 // left child
right = 2 * i + 2 // right child
// If left child is larger than root
if left < n and arr[left] > arr[largest]:
largest = left
// If right child is larger than largest so far
if right < n and arr[right] > arr[largest]:
largest = right
// If largest is not root
if largest != i:
swap arr[i] with arr[largest]
// Recursively heapify the affected sub-tree
heapify(arr, n, largest)
// Utility function to swap two elements in an array
function swap(a, b):
temp = a
a = b
b = temp