Heap Sort in Ascending Order in Python

1. Introduction

In this blog post, we will learn how to write a Python program to sort an array of integers in an Ascending Order using the Heap Sort algorithm.

Heap Sort is a powerful comparison-based sorting algorithm that leverages the properties of a binary heap. By converting the list into a max heap (a binary tree where each parent has a value greater than or equal to its children), this algorithm ensures that the largest value is moved to the end of the list. This process is repeated for the remaining elements.

2. Program Overview

1. heapify(): Converts the list into a binary heap.

2. heap_sort(): Primary function that orchestrates the Heap Sort process.

3. A sample list to showcase the sorting mechanism.

3. Code Program

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

    # Check if left child exists and is larger than the root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # Check if right child exists and is larger than the largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right

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

        # Recursively heapify the affected sub-tree
        heapify(arr, n, largest)

def heap_sort(arr):
    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):
        # Swap current root with end
        arr[i], arr[0] = arr[0], arr[i]

        # Heapify the reduced heap
        heapify(arr, i, 0)

def print_list(arr):
    for i in arr:
        print(i, end=" ")
    print()

# Driver segment to test the functions
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Unsorted list is:")
    print_list(arr)

    heap_sort(arr)

    print("\nList sorted in ascending order is:")
    print_list(arr)

Output:

Unsorted list is:
64 34 25 12 22 11 90 

List sorted in ascending order is:
11 12 22 25 34 64 90 

4. Step By Step Explanation

1. heapify(): A function that upholds the heap property. If the parent node violates the heap property with its children, this function swaps them.

2. heap_sort(): First, it constructs the initial heap. After the max heap is built, the maximum element (present at the root) is moved to the end using a swap. This step is repeated for the rest of the items.

3. print_list(): A utility function to print out the list items.

4. Driver segment: Provides a demonstration of Heap Sort's capabilities using a sample list.

Heap Sort is particularly beneficial when dealing with large datasets, offering a consistent O(n log n) time complexity.

Related Python Programs on Sorting Algorithms

1. Bubble Sort in Ascending Order in Python
2. Bubble Sort in Descending Order in Python
3. Selection Sort in Ascending Order in Python
4. Selection Sort in Descending Order in Python
5. Insertion Sort in Descending Order in Python
6. Insertion Sort in Ascending Order in Python
7. Merge Sort in Ascending Order in Python
8. Merge Sort in Descending Order in Python
9. Quick Sort in Ascending Order in Python
10. Quick Sort in Descending Order in Python
11. Heap Sort in Ascending Order in Python
12. Heap Sort in Descending Order in Python