Question

Write an algorithm and p9rogram accepts the following list of integers and uses Heap Sort to

sort and print them:



6, 2, 9, 12, 89, 34, 99, 3, 100​

Answer 1

Answer:

99+100

Explanation:

6+2+9+12+89+34+99+100

Answer 2

Heap Sort Algorithm for sorting in increasing order:

1. Build a max heap from the input data.

2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of the tree.

3. Repeat step 2 while size of heap is greater than 1.

# Python program for implementation of heap Sort  

# To heapify subtree rooted at index i.  

# n is size of heap  

def heapify(arr, n, i):  

largest = i # Initialize largest as root  

l = 2 * i + 1  # left = 2*i + 1  

r = 2 * i + 2  # right = 2*i + 2  

# See if left child of root exists and is  

# greater than root  

if l < n and arr[i] < arr[l]:  

 largest = l  

# See if right child of root exists and is  

# greater than root  

if r < n and arr[largest] < arr[r]:  

 largest = r  

# Change root, if needed  

if largest != i:  

 arr[i],arr[largest] = arr[largest],arr[i] # swap  

 # Heapify the root.  

 heapify(arr, n, largest)  

# The main function to sort an array of given size  

def heapSort(arr):  

n = len(arr)  

# Build a maxheap.  

for i in range(n//2 - 1, -1, -1):  

 heapify(arr, n, i)  

# One by one extract elements  

for i in range(n-1, 0, -1):  

 arr[i], arr[0] = arr[0], arr[i] # swap  

 heapify(arr, i, 0)  

# Driver code to test above  

arr = [ 6, 2, 9, 12, 89, 34, 99, 3, 100]  

heapSort(arr)  

n = len(arr)  

print ("Sorted array is")  

for i in range(n):  

print ("%d" %arr[i]),