Question

Part A

Write a 6-8 sentence summary explaining how you can use the Heap Sort algorithms to solve a real world problem. In your summary, provide a descriptive or visual explanation of your heapsort solution.

Part B

For this portion of the assignment you will design an algorithm to implement the solution described in part A. Your algorithm must be written in pseudocode.

Note:

Sample HeapSort Algorithm Pseudocode:

Heapsort(A as array)
    BuildHeap(A)
    for i = n to 1
        swap(A[1], A[i])
        n = n - 1
        Heapify(A, 1)

BuildHeap(A as array)
    n = elements_in(A)
    for i = floor(n/2) to 1
        Heapify(A,i,n)

Heapify(A as array, i as int, n as int)
    left = 2i
    right = 2i+1

    if (left <= n) and (A[left] > A[i])
        max = left
    else 
        max = i

    if (right<=n) and (A[right] > A[max])
        max = right

    if (max != i)
        swap(A[i], A[max])
        Heapify(A, max)

Answer 1

1).ANSWER:

GIVEN THAT:

Part 1

Heap sort is a sorting algorithm. This algorithm uses the binary heap data structure which is a complete binary tree.Here, first we create a tree data structure using the arrays.For creating tree from the array, we will make the element at the index 2i+1 as left child and at the index 2i+2 as right child of the tree.A max-heap is created by using the function heapify.Max-heap means the largest element will be at root node and both the children are smaller than the root node.After creating the max-heap, we will swap the element at the root node with the last element of the array.Now heapify the the max-heap by removing that last element.Repeat these step until array get sorted.

Part 2

Heapify(Arr as array, n as int, i as int)

{

max = i

left = 2i + 1

right = 2i + 2

if (left<= n) and (Arr[i] < Arr[left])

max = left

else

max = i

if (right <= n) and (Arr[max] > Arr[right])

max = right

if (max != i)

swap(Arr[i], Arr[max])

Heapify(Arr, n, max)

}

Heapsort(Arr as array)

{

n = length(Arr)

for i = n/2 to 1

Heapify(Arr, n ,i)

for i = n to 2

swap Arr[1] with Arr[i]

Arr.heapsize = Arr.heapsize - 1

Heapify(Arr, i, 0)

}