Question

Explain how you can utilize a minimum heap to sort the list of number in descending order. Let n-be the number of elements in the list. What is the complexity of your sorting algorithm.Explain how you can utilize a minimum heap to sort the list of number in descending order. Let n-be the number of elements in the list. What is the complexity of your sorting algorithm.Please explain through example and give algorithem in written form (no code).

Answer 1

Heap sort is made up of two phases:

Phase 1: Construct a heap using the given elements.

Phase 2: Perform Continuous deletion of root element from the heap.

Heap Sort using min heap sorts in descending order where as max heap sorts in ascending order

Operations on utilizing Minimum Heap to sort the list of numbers in descending order:

1) getMini(): It returns the root element of Min Heap. Time Complexity of this operation is O(1).

2) extractMin(): Removes the minimum element from MinHeap. Time Complexity of this Operation is O(Logn) as this operation needs to maintain the heap property (by calling heapify()) after removing root.

3) decreaseKey(): Decreases value of key. The time complexity of this operation is O(Logn). If the decreases key value of a node is greater than the parent of the node, then we don’t need to do anything. Otherwise, we need to traverse up to fix the violated heap property.

4) insert(): Inserting a new key takes O(Logn) time. We add a new key at the end of the tree. IF new key is greater than its parent, then we don’t need to do anything. Otherwise, we need to traverse up to fix the violated heap property.

5) delete(): Deleting a key also takes O(Logn) time. We replace the key to be deleted with minum infinite by calling decreaseKey(). After decreaseKey(), the minus infinite value must reach root, so we call extractMin() to remove the key.

Time complexity :

n being the number of elements in the given list

It takes O(logn) for heapify and O(n) for constructing a heap. Hence, the overall time complexity of heap sort using min heap or max heap is O(nlogn)

Algorithm with example below :

1. Build a min heap from the input data.
2. At this point, the smallest 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.

3. Heapify the root of tree.
4. Repeat above steps while size of heap is greater than 1.

Example