Ques. Write a program to implement Heap Sort
Answer : Heap sort is a sorting algorithm in which elements are sorted using maximum or minimum heap .Minimum heap represents the ordering of the array in which root element represents the minimum element of the array and Maximum heap represents the ordering of the array in which root element represents the maximum element of the array. Heap is a Complete Binary Tree in which all the elements are stored in a order such that value in a parent node is maximum or minimum than the values in its two children nodes. The one in which root element is maximum ,then it is called as max heap and the one in which root element is the minimum then it is called min heap. The heap can be represented by an array.
Example :
|
A: 40, 100, 30, 50, 10
40(0)
/ \
100(1) 30(2)
/ \
5(30) 10(4)
The numbers in bracket represent indexes to the elements .
if we Apply heap procedure to index 1:
40(0)
/ \
100(1) 30(2)
/ \
50(3) 10(4)
If we Apply heap procedure to 0 index:
100(0)
/ \
50(1) 30(2)
/ \
40(3) 10(4)
heap procedure calls itself recursively to build heap
in top down manner.
|
Program :
|
def heap(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]
heap(arr, n, largest)
def heap(arr):
n = len(arr)
for i in range(n, -1, -1):
heap(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heap(arr, i, 0)
a=input("enter elements : ")
arr = a.split(",")
heapS(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
print (arr[i],end=" ")
|
Program :
Output :
enter elements : 1,6,2,4,3,0,8
Sorted array is
0 1 2 3 4 6 8
For more Rajasthan Technical University CSE-III Sem DSA Lab Experiments CLICK HERE
| 
| 
