# 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).