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

Answer:

A heap sort can be implemented as a priority queue.

It can be used to quickly find the smallest and largest element from a collection of items or array.

It can be used in the implementation of the Priority queue in graph algorithms like Dijkstra's algorithm (shortest path), Prim's algorithm (minimum spanning tree) and Huffman encoding (data compression).

In order to overcome the Worst-Case Complexity of Quick Sort algorithm from O(n^2) to O( nlog(n) ) in Heap Sort.

For finding the order in statistics.

Systems concerned with security and embedded system such as Linux Kernel uses Heap Sort because of the O( nlog(n) ).

Instead of just joining a queue at its tail, a person or object may be inserted further up the queue depending on their priority.

Algorithm for heap sort:

Start
Heap sort():
{
 for each value from n/(2-1) to 0:
 {
    heapify (array, n and i)
    for each value from n-1 to 0:
    {
       swap the values in an array;
       Then again heapify (arr, i, 0);
    }
}

Let me know if you have any doubts or if you need anything to change. 

If you are satisfied with the solution, please leave a +ve feedback : ) Let me know for any help with any other questions.

Thank You!
===========================================================================