Heap Sort in Descending 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 a Descending Order using the Heap Sort algorithm.

Heap Sort is a comparison-based sorting algorithm that employs the properties of a binary heap. To sort in descending order, we will utilize a min-heap (a binary tree where each parent has a value less than or equal to its children). This algorithm ensures that the smallest value is moved to the end of the list. This process is then repeated for the remaining elements.

2. Program Overview

1. heapify(): Transforms the list into a binary min-heap.

2. heap_sort(): The main function responsible for implementing the Heap Sort.

3. A sample list is provided to illustrate the sorting mechanism.

3. Code Program

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

    # Check if left child exists and is smaller than the root
    if left < n and arr[left] < arr[smallest]:
        smallest = left

    # Check if right child exists and is smaller than the smallest so far
    if right < n and arr[right] < arr[smallest]:
        smallest = right

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

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

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

    # Build a min 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 descending order is:")
    print_list(arr)

Output:

Unsorted list is:
64 34 25 12 22 11 90 

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

4. Step By Step Explanation

1. heapify(): This function ensures the heap property is maintained. If a parent node does not adhere to the heap property with its children, the function will swap them.

2. heap_sort(): First, an initial min-heap is constructed. Once the min-heap is established, the smallest element (located at the root) is moved to the end through a swap. This step is repeated for all remaining items.

3. print_list(): A simple function to display the elements of the list.

4. Driver segment: Illustrates the power of Heap Sort using a sample list.

The descending Heap Sort, using a min-heap, proves beneficial for datasets of substantial size, operating consistently at a time complexity of O(n log n).

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