Latest
Home » Heap Sort Algorithm in Python

Heap Sort Algorithm in Python

Hello Python enthusiasts, welcome back to Programming In Python. I am back with another sorting algorithm, here I will try to discuss on Heap Sort Algorithm in Python.

Introduction

Heap sort is an efficient sorting algorithm that works by first organizing the data to be sorted into a binary heap. Then, the root element of the heap is removed and placed at the end of the sorted array. The heap is then reconstructed with the remaining elements, and the process repeats until the heap is empty. In this tutorial, we’ll be implementing the Heap sort algorithm in Python.

Step 1: Understanding the Binary Heap

Before we can implement Heap sort, we need to understand what a binary heap is. A binary heap is a complete binary tree in which every parent node has two child nodes, and the key value of the parent node is less than or equal to the key values of its child nodes (in a “min heap”). The root node of the binary heap is the smallest element in the heap.

To represent a binary heap in Python, we can use an array or a list. For example, the following list represents a binary heap:

`[4, 7, 9, 10, 8, 5, 1, 3, 2, 6]`

In this list, the root node is 4, and the child nodes are 7 and 9. The next level of nodes contains 10, 8, 5, and 1. And the final level contains 3, 2, and 6.

Step 2: Implementing the Heapify Function

The first step in implementing Heap sort is to write a function that “heapifies” a binary tree. The heapify function takes an array or list and an index as input, and it recursively swaps elements until the heap property is satisfied. Here’s an implementation of the heapify function:

```def heapify(arr, n, i):
largest = i  # Initialize largest as root
l = 2 * i + 1  # left = 2*i + 1
r = 2 * i + 2  # right = 2*i + 2

# See if left child of root exists and is greater than root
if l < n and arr[i] < arr[l]:
largest = l

# See if right child of root exists and is greater than root
if r < n and arr[largest] < arr[r]:
largest = r

# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]  # swap

# Heapify the root.
heapify(arr, n, largest)
```

Here, arr is the input array, n is the size of the heap, and i is the index of the root node. The function first initializes the largest variable to the index of the root node. It then calculates the indices of the left and right child nodes, and checks whether they are greater than the root node. If either child node is greater, the function swaps the root node with the larger child node, and recursively calls itself on the child node.

Ad:
Python for Finance: Investment Fundamentals & Data Analytics – Enroll Now.
Udemy

Step 3: Implementing Heap Sort

Now that we have a function to heapify the binary tree, we can use it to implement Heap sort. Here’s an implementation of the Heap sort algorithm:

```def heap_sort(arr):
n = len(arr)

# Build a maxheap.
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)

# Extract elements one by one
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]  # swap
heapify(arr, i, 0)
```

Here, the function first initializes the n variable to the length of the input array. It then builds a max heap by calling the heapify function on the array in reverse order from the middle to the start. Finally, the function extracts elements from the max heap one by one and places them at the end of the sorted array, while maintaining the heap property.

Step 4: Testing the Implementation

Now that we’ve implemented Heap sort, let’s test it out on a sample array. Here’s a sample array we’ll use for testing:

`arr = [12, 11, 13, 5, 6, 7]`

To sort this array using Heap sort, we can simply call the `heap_sort` function on the array:

```heap_sort(arr)
print("Sorted array is:")
print(arr)```

This should output the following sorted array:

```Sorted array is:
[5, 6, 7, 11, 12, 13]```

Heap Sort Algorithm in Python: Full Program

```def heapify(arr, n, i):
"""
Heapify function to build a max heap from an unsorted array.
"""
largest = i  # Initialize largest as root
l = 2 * i + 1  # left = 2*i + 1
r = 2 * i + 2  # right = 2*i + 2

# See if left child of root exists and is greater than root
if l < n and arr[l] > arr[largest]:
largest = l

# See if right child of root exists and is greater than root
if r < n and arr[r] > arr[largest]:
largest = r

# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]  # swap

# Heapify the root.
heapify(arr, n, largest)

def heap_sort(arr):
"""
Heap sort function to sort an unsorted array in ascending order.
"""
n = len(arr)

# Build a max heap.
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)

# Extract elements one by one
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]  # swap
heapify(arr, i, 0)

# Print the sorted list
print('\nThe sorted list: \t', arr)
print('\n')

lst = []
size = int(input("\nEnter size of the list: \t"))

for input_elements in range(size):
elements = int(input("Enter the element: \t"))
lst.append(elements)

heap_sort(lst)
```

Output

Ad:
Python for Finance: Investment Fundamentals & Data Analytics – Enroll Now.
Udemy

Conclusion

Heap sort is an efficient sorting algorithm that works by organizing the data to be sorted into a binary heap, and then repeatedly extracting elements from the heap and placing them in the sorted array. In this tutorial, we’ve implemented Heap sort in Python by first writing a function to heapify a binary tree, and then using that function to implement Heap sort. We’ve also tested our implementation on a sample array and verified that it correctly sorts the array.