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.

Program on GitHub

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.

Initial Heap - Binary tree — Initial Heap – Binary tree

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]

Program on GitHub

Code Visualization