Heap sort in Python

Python heap sort program

In this program, we will learn to develop a code using heap sort.

Heap Sort is a technique that is based on a binary heap data structure. It is a comparison-based sorting technique which is similar to selection sort. Thus we need to find the maximum element and place it at the end. We repeat the same process for the remaining element.

Algorithm:

1. Define a function heapify(arr, n, i).
2. The variable largest is assigned the value of i.
3. l and r is also assigned the value 2 * i + 1 and  2 * i + 2 respectively.
4. Using if statement, if l<n and arr[i] < arr[l] then, l is assigned to largest variable.
5. Using if statement, if r<n and arr[largest] < arr[r] then, r is assigned to largest variable.
6.  If largest != I then, arr[i],arr[largest] = arr[largest],arr[i].  
7. Define another function named heapSort(arr).
8. Length of array is assigned to variable n.
9.  Using for loop, with  range(n, -1, -1), call heapify(arr, n, i). 
10. Using for loop, with  range(n-1, 0, -1), call heapify(arr, n, 0) .
11. Initialize the array and call the function heapSort(arr).
12. Print the sorted array.
13. Exit .

Code:

def heapify(arr, n, i): 
    largest = i   
    l = 2 * i + 1
    r = 2 * i + 2
  
    if l < n and arr[i] < arr[l]: 
        largest = l 
  
    if r < n and arr[largest] < arr[r]: 
        largest = r 
        
    if largest != i: 
        arr[i],arr[largest] = arr[largest],arr[i]   
  
        heapify(arr, n, largest) 
  
def heapSort(arr): 
    n = len(arr) 
    for i in range(n, -1, -1): 
        heapify(arr, n, i) 
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i]  
        heapify(arr, i, 0) 
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])

Output:

Sorted array is:
5
6
7
11
12
13