Python Program to Implement Heap Sort

«
»

This is a Python program to implement heapsort.

Problem Description

The program sorts a list by heapsort.

Problem Solution

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.

Program/Source Code

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

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)
Program Explanation

1. The user is prompted to enter a list of numbers.
2. The list is passed to the heapsort function.
3. The sorted list is displayed.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
Runtime Test Cases
Case 1:
Enter the list of numbers: 3 2 2 1 0 -2 5 7
Sorted list: [-2, 0, 1, 2, 2, 3, 5, 7]
 
Case 2:
Enter the list of numbers: 5 4 3 2 1
Sorted list: [1, 2, 3, 4, 5]
 
Case 3:
Enter the list of numbers: 1
Sorted list: [1]

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.