Heap Sort Program in Python Language

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 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 heap sort algorithm is divided into two basic parts:

• Creating a Heap of the unsorted list/array.
• Then a sorted array is created by repeatedly removing the largest/smallest element from the heap, and inserting it into the array. The heap is reconstructed after each removal.

As the output, we are required to get the sorted array.

Look at the given example to understand the working with input and output.

Input:

array: {3 5 1 2 6}

Output:

array: {1 2 3 5 6}

Input:

array: {56 9 11 7 60}

Output:

array: {7 9 11 56 60}

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

Heap Sort Program in Python Language

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

We have concluded the significance of heap sort in this tutorial. Also, the implementation part has been shown to produce the program's desired output.