Implement Heap Sort in Python

If you’re in a computer science background, widening your technical horizons is the best thing you should do. However, your programming skills matter the most. And one must continuously keep sharpening these skills, to become a better programmer in the future. Though there are multiple things to focus on, one specific area you must focus on is the world of data structures. Data structures in general are particular approaches to solve problems so that computer resources get used minimum. In general, there are multiple data structures you can learn and implement as well. However, we’ve covered some basic data structures before, so, now we’ll move towards some advanced data structures. Hence, today we’re going to learn how to Implement Heap Sort using Python.

 

What is Heap Sort?

 

• It is a comparison-based sorting algorithm that works on the principles of Binary Heap data structure.

 

• The algorithm creates a heap of input elements similar to that of binary trees. Elements are divided into sorted and unsorted heaps.

 

• The largest elements are moved from the unsorted heap to the sorted heap. So the smallest element is kept at the top.

 

• And this process is repeated further till the entire heap gets sorted.

 

Also Read: Implement Bubble Sort using Python

 

What’s The Approach?

 

• Firstly we’ll divide our input array into two parts i.e, inside the heapify() function.

 

• While doing so, we are going to start from the middle of the input array, and with each iteration, we’re going to decrement the index i by one.

 

• While creating heaps, we’ll make sure to keep the largest element as the root (head element).

 

• The above two instructions will continue to execute till we reach the starting index of the array.

 

• At the end of the heapify() function, use recursion to sort the sub-heaps as well.

 

Python Program To Implement Heap Sort

 

INPUT:

12, 11, 13, 5, 6, 7

 

OUTPUT:

Sorted array is 
5 6 7 11 12 13 

 

# Python program for implementation of heap Sort

# To heapify subtree rooted at index i.
# n is size of heap
def heapify(arr, n, i):
    largest = i # Initialize largest as root
    l = 2 * i + 1	 # left = 2*i + 1
    r = 2 * i + 2	 # right = 2*i + 2

    # See if left child of root exists and is
    # greater than root
    if l < n and arr[largest] < arr[l]:
        largest = l

    # See if right child of root exists and is
    # greater than root
    if r < n and arr[largest] < arr[r]:
        largest = r

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

        # Heapify the root.
        heapify(arr, n, largest)

# The main function to sort an array of given size


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

    # Build a maxheap.
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)

    # One by one extract elements
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i] # swap
        heapify(arr, i, 0)


# Driver code
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
    print("%d" % arr[i]),