Table of Contents
In this article, you will learn how to sort elements in an array using the heap sort algorithm. It is one of the efficient comparison-based sorting algorithms, which performs in-place sorting.
The algorithm of the heap sort is based on the heap data structure. So, what is it? Before going there, let’s take a look at a complete binary tree is.
Complete Binary Tree
A binary tree in which all the levels are completely filled, except possibly the last one. Furthermore, they always get filled from left to right.
Heap Data Structure
The heap data structure is of two types, and the heap property also depends upon it.
- Max Heap: In this type, the value of the parent node is always greater than or equal to the values of its children. Therefore, the value at the root will be maximum.
- Min Heap: In this type, the value of the parent node is always smaller than or equal to the values of its children. Thus, the root node will have the minimum value.
We can easily represent a complete binary tree or a heap by an array. If the parent is at index i, then the left child will be at index 2 x i+1, and the right child will be at index 2 x i+2. Moreover, if i is a child, then its parent will be at index (i-1)/2 (integer division).
Build a Max Heap
Let’s see how we can build a max heap from a complete binary tree stored in an array. Let the length of the array be n.
- We will start from the last non-leaf node (at index n/2-1) and go all the way up to the root node. For each such node, we will call the heapify method.
- The heapify method is recursive; it takes a root node of a subtree and generates a maximum heap at that level. To be more specific, it compares the root element with its children. If any child is greater than the root node, then it swaps the values of both nodes. The swapped node gets pushed down until it reaches its correct position.
We can easily generate a min-heap using a similar approach. We only have to change the comparison condition so that the parent node has a smaller value than its children. However, in this article, we will use the max heap.
Now that we know how to build a max heap, let’s go ahead and see how we can sort the array.
Implementation of the Heap Sort Algorithm
- First, we build a max heap from the input array. Thus, the maximum value will be at the root, at index 0.
- We swap the maximum value with the last element and decrease the size of the array by 1. Then, we call the heapify method to get the maximum value at the root. This process continues until the size of the array is greater than 1.
The Code
def heapify(array, length, i):
maximum=i
left_child=2*i+1
right_child=2*i+2
if (left_child < length and array[left_child]>array[maximum]): #if the left child exists and it is greater than the parent
maximum = left_child #set the maximum to the left child
if (right_child < length and array[right_child]>array[maximum]): #if the left child exists and it is greater than the element at index maximum
maximum=right_child #set the maximum to the right child
if (maximum != i): #swap if the value of child(ren) > parent
array[maximum], array[i] = array[i], array[maximum]
heapify(array, length, maximum) #heapify the subtree
def maximumHeap(array, length):
end = (length//2)-1
for i in range(end, -1, -1): #run the loop from non-leaf nodes to the root node
heapify(array, length, i)
def heapSort(array, length):
maximumHeap(array, length) # build the maximum heap
for i in range(len(array)-1, 0, -1):
array[i], array[0]=array[0], array[i] #We swap the maximum value with the last element
heapify(array, i, 0) #heapify the new root
array=[6,1, 3, 4, 9, 23, 33, 8]
heapSort(array, len(array))
print("Sorted Array:", array) #sorted array
Output
Sorted Array: [1, 3, 4, 6, 8, 9, 23, 33]
The time complexity of heap sort is O(nlogn) in the best, average, and worst cases.