Write a program to implement Heap Sort

0 like 0 dislike
336 views

recategorized

Write a program to implement Heap Sort

0 like 0 dislike
by Goeduhub's Expert (7.6k points)
edited

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

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.