Write a Python program to implement heap sort and use it to sort a list.

Heapsort in Python is a sorting algorithm that utilizes a binary heap data structure to efficiently sort elements in an array.

Let’s say we have an unsorted list of numbers: **[8, 5, 3, 9, 1]**.

**Step 1: Heap Construction**

- First, we construct a binary heap from the list. This step rearranges the elements in the list to satisfy the heap property, which means that each parent node is greater than or equal to its children.
- After constructing the heap, the list becomes:
**[9, 5, 8, 3, 1]**.

**Step 2: Repeated Extraction of Maximum**

- In this step, we repeatedly extract the maximum element from the heap and place it at the end of the list.
- In each extraction, we swap the maximum element (root of the heap) with the last element in the list. Then, we reduce the heap size by one and heapify the reduced heap to maintain the heap property.
- After the first extraction, the list becomes:
**[1, 5, 8, 3, 9]**. - After the second extraction, the list becomes:
**[1, 3, 8, 5, 9]**. - After the third extraction, the list becomes:
**[1, 3, 5, 8, 9]**. - Now, the list is sorted in ascending order.

That’s how Heap Sort works. It uses the heap data structure to efficiently sort the elements in the list.

Here is the source code of a Python program to implement heapsort. The program output is shown below.

# Python Program to Implement Heapsort def heapsort(alist): build_max_heap(alist) for i in range(len(alist) - 1, 0, -1): alist[0], alist[i] = alist[i], alist[0] max_heapify(alist, index=0, size=i) def parent(i): return (i - 1)//2 def left(i): return 2*i + 1 def right(i): return 2*i + 2 def build_max_heap(alist): length = len(alist) start = parent(length - 1) while start >= 0: max_heapify(alist, index=start, size=length) start = start - 1 def max_heapify(alist, index, size): l = left(index) r = right(index) if (l < size and alist[l] > alist[index]): largest = l else: largest = index if (r < size and alist[r] > alist[largest]): largest = r if (largest != index): alist[largest], alist[index] = alist[index], alist[largest] max_heapify(alist, largest, size) alist = input('Enter the list of numbers: ').split() alist = [int(x) for x in alist] heapsort(alist) print('Sorted list: ', end='') print(alist)

1. Create a function **heapsort** that takes a list as argument.

2. Call **build_max_heap** with the list as argument to rearrange the list into a list representation of a heap.

3. Swap the first element with the last element in the heap.

4. Consider the new heap to have size one less than its previous size and call **max_heapify** with index = 0 to make this new heap satisfy the heap property.

5. Repeat steps 3 and 4 until the size of the heap reduces to zero and the entire list is sorted.

6. Define the function **parent** that takes an index as argument and returns the index of the parent.

7. Define the function **left** that takes an index as argument and returns the index of its left child.

8. Define the function **right** that takes an index as argument and returns the index of its right child.

9. Define the function **build_max_heap** that takes a list as argument and rearranges it to form a max heap.

10. The **build_max_heap** function works by calling **max_heapify** on each parent node starting from the last parent node and working towards the root.

11. Define the function **max_heapify** that takes an index as argument and modifies the heap structure at and below the node at this index to make it satisfy the heap property.

12. The user is prompted to enter a list of numbers.

13. The list is passed to the **heapsort** function.

14. The sorted list is displayed.

**Time Complexity: O(n log n)**

The time complexity of the heapsort function is O(n log n), where n is the length of the input list, as it involves multiple iterations over the list for heap construction and repeated extraction of the maximum element.

**Space Complexity: O(1)**

The space complexity of Heap Sort in Python is O(1) as it sorts the list in-place without requiring any additional memory proportional to the input size.

**Testcase 1:** In this case, we are performing heap sort operation. The given list has the values 8, 5, 3, 9, 1

Enter the list of numbers: 3 2 2 1 0 -2 5 7 Sorted list: [-2, 0, 1, 2, 2, 3, 5, 7]

**Test case 2:** In this scenario, we are applying the heap sort operation to a given list containing the values 5, 4, 3, 2, and 1.

Enter the list of numbers: 5 4 3 2 1 Sorted list: [1, 2, 3, 4, 5]

To practice programs on every topic in Python, please visit “Programming Examples in Python”.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Practice Programming MCQs
- Apply for Python Internship
- Check Python Books
- Apply for Programming Internship
- Check Information Technology Books