{"post":"

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:

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

Code:

def heapify(arr, n, i): \n    largest = i   
\n    l = 2 * i + 1
\n    r = 2 * i + 2
\n  
\n    if l < n and arr[i] < arr[l]: 
\n        largest = l 
\n  
\n    if r < n and arr[largest] < arr[r]: 
\n        largest = r 
\n        
\n    if largest != i: 
\n        arr[i],arr[largest] = arr[largest],arr[i]   
\n  
\n        heapify(arr, n, largest) 
\n  
\ndef heapSort(arr): 
\n    n = len(arr) 
\n    for i in range(n, -1, -1): 
\n        heapify(arr, n, i) 
\n    for i in range(n-1, 0, -1): 
\n        arr[i], arr[0] = arr[0], arr[i]  
\n        heapify(arr, i, 0) 
\narr = [ 12, 11, 13, 5, 6, 7] 
\nheapSort(arr) 
\nn = len(arr) 
\nprint (\"Sorted array is:\") 
\nfor i in range(n): 
\n    print (\"%d\" %arr[i])

Output:

Sorted array is:\n5 \n6 \n7 \n11 \n12 \n

13

\n","title":"Heap sort in Python","authorDetails":{"name":"Himani Kohli","slug":"himani-kohli"},"seo":{"title":"Heap sort in Python"},"description":"Here we'll learn to write a program to sort an array using heap sort in python with example and algorithm. Heap Sort is a comparison-based sorting technique that 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.","slug":"python/examples/heap-sort-program-in-python/","articleId":"636a83457bb1ce5072622bc1","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}