Updated April 17, 2023
Introduction to Heap Sort in Python
Heap sort is one of the many data structuring techniques used for sorting the data/ elements, which involves the process of continuously ordering the largest number/ character in the list to the last position until the whole list is completely sorted in ascending order. A python is an object-oriented programming language that offers pre-defined methods for arithmetic and logical operations that can be applied to any kind of data/element in the program. In a Python program, Heap sort can be logically attained using the functions like count(), len(), max(), range(), etc.
How does Heap Sort work in Python?
- Before Explaining the Working of Python, It Is Important to Understand What Actually It Is and How It Is Different from Other Sorting Algorithms. Heapsort Can Be Considered as The Sorting Approach in Which the Maximum Value from The List Is Encountered and Shifted to The Last of The Array and The Process Is Kept on Repeating Till the List Is Transformed Into a Sorted List. The Way that Makes It Different from The Other Sorting Methods Is Nothing but Just the Approach that It Follows in Order to Sort All the Values of The Array. It Consists of The Recursive Process that Lasts until The Values in The Array Are Arranged in Ascending Order.
- Now let us understand how the heap sort works in detail by using an example. Suppose arr is an array that holds the values like 9,5,2. In the beginning, the values of the array are not arranged in a sorted way, but after performing the heap sort, it will be turned into ascending order. When the heap sort algorithm is applied to this array, the first thing it will do is find our the largest value in the array. As 9 is the largest value, it will be moved to the last index of the list, and all the other values will move one step left in order to create space for holding the largest value. Once 9 is shifted to the last index or array arr, the list of values will look like 5,2,9.
- The array is still not sorted, which indicates that the same process has to be repeated again. Now while finding the largest value from the list of unprocessed values, 5 will be selected as the second-largest value and will be moved to the second last index. After moving 5 at the second last position, the array will be turned into a sorted array, and the values will be arranged in the assembly ascending order like 2,5,9. This is the way heap sort works. In actual terms, it identifies the maximum value and moves it to the end of the array and keeps on performing the same process until the array turns into the sorted array.
Examples to Implement Heap Sort in Python
To learn the concept of heapsort, let us understand it using the actual example. We will be implementing the heap sort algorithm using the python language. In order to develop the program, we will be using the for loop to bring the recursion mechanism and will be using if conditions checking to verify the conditions. In the below code, perform_heapsort is the function that accepts three arguments: val_arr, num and count, where var_arr is the array while num and count are of an integer data type. The idea of the below code is to find the largest number and hold it temporarily in the max_val variable until it gets shifted to the end of the array. If a statement has been used to ensure that the largest value is getting shifted to the appropriate position and that position is being blocked from getting updated by the next largest value in the list. The program will repeat the approach of finding the largest value and shifting it to the end until the list turns into the sorted one.
Code:
def perform_heapsort(val_arr, num, count):
max_val = count
counter1 = 2 * count + 1
counter2 = 2 * count + 2
if counter1 < num and val_arr[count] < val_arr[counter1]:
max_val = counter1
if counter2 < num and val_arr[max_val] < val_arr[counter2]:
max_val = counter2
if max_val != count:
val_arr[count],val_arr[max_val] = val_arr[max_val],val_arr[count]
perform_heapsort(val_arr, num, max_val)
def heapSort(val_arr):
num = len(val_arr)
for count in range(num, -1, -1):
perform_heapsort(val_arr, num, count)
for count in range(num-1, 0, -1):
val_arr[count], val_arr[0] = val_arr[0], val_arr[count] # swap
perform_heapsort(val_arr, count, 0)
val_arr = [ 52, 91, 64, 252, 36, 91, 5, 35, 28]
heapSort(val_arr)
num = len(val_arr)
print ("Values after performing heapsort")
for count in range(num):
print ("%d" %val_arr[count]),In this program, the values have been assigned manually through the code. The var_arr is the array that holds the values. In this example, we have assigned 9 values to the array. The values in the array will be passed to the method named perform_heapsort. Once the values enter the method, they will be processed, and the program will start finding the largest value from the list. The maximum value in this array is 252, so it will be shifted to the end of the array, and this process will be applied to all the values till the array turns into the sorted array. Once the program sorts the array, the output will be displayed in the output.
Output:
Conclusion
Heapsort is one of the various sorting algorithms. The eventual output of this algorithm is the sorted list which has the data arranged in ascending order. As the process is repeated and all the values are shifted to the left to adjust the maximum value of the list at the end of the array, it is considered the less efficient sorting algorithm. This approach of sorting can be leveraged in the application that is supposed to process a small number of values.
Recommended Articles
We hope that this EDUCBA information on “Heap Sort in Python” was beneficial to you. You can view EDUCBA’s recommended articles for more information.
