Python Program for Heap Sort

Heapsort is a sorting algorithm based on comparison and a Binary Heap data structure. In this tutorial, we will sort an array with help of the heapsort algorithm.

Heap Data Structure - A basic Introduction

Heap is a type of data structure that is based on trees. A priority queue is represented by a heap data structure. A binary tree is said to follow a heap data structure if:

• all nodes in the tree are greater than their children in the tree.
• It will be a complete binary tree.

Max-heap: - When each parent node is less than or equal to child nodes.

Min-heap: - When each parent node is greater than or equal to child nodes.

The below diagram will reflect max-heap and min-heap for better understanding:

Heap Sort - Working

The heapsort is similar to the selection sort in that we locate the maximum element first and then place it at the end but In heap sort , we repeat the same process for the remaining element. It follows three main steps which are as follows:

1. Swap: It removes the root element from the array and places it at the end (nth position) Place the tree's last item (heap) in the empty spot.
2. Remove: The size of the heap is reduced by 1
3. Heapify: It uses recursion, Hepify the root element once more such that the highest element is at the root

In the heapsort algorithm to sort an array, we have to repeat the above process until the list is sorted.

Algorithm

As of now, we have a rough understanding of how heap sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Define a function heapify()
2. Pass three parameters array, a and b
3. Find largest among root and children
4. If the root is not the largest, swap it with children
5. Continue to heapify
6. Define function Heap_Sort()
7. Pass array as a parameter
8. Build Max-heap and swap
9. Heapify the root element
10. The result will be the sorted array
11. Print the result

Program for Heap Sort

As discussed above in the algorithm, let us now dive into the programming part of the Heap Sort operation influenced by the algorithm.

def heapify(array, a, b):
	largest = b 
	l = 2 * b + 1
	root = 2 * b + 2	 

	if l < a and array[b] < array[l]:
		largest = l

	if root < a and array[largest] < array[root]:
		largest = root

	# Change root
	if largest != b:
	    array[b], array[largest] = array[largest], array[b]
	    heapify(array, a, largest)

# sort an array of given size
def Heap_Sort(array):
	a = len(array)

	# maxheap..
	for b in range(a // 2 - 1, -1, -1):
		heapify(array, a, b)

	# extract elements
	for b in range(a-1, 0, -1):
		array[b], array[0] = array[0], array[b] # swap
		heapify(array, b, 0)

# Driver code 
array = [ 7, 2, 5, 6, 3, 1, 8, 4]
print("The original array is: ", array)
Heap_Sort(array)
a = len(array)
print ("Array after sorting is: ", array)

The original array is: [7, 2, 5, 6, 3, 1, 8, 4]
Array after sorting is: [1, 2, 3, 4, 5, 6, 7, 8]

Conclusion

In this tutorial, we have performed a Heap Sort sort operation in python to sort an array. The heapsort algorithm doesn't have stability. The time complexity of the heapsort algorithm is O(n log n) and the space complexity is O(1).