Question

Answer the following questions:

a) Show (diagrammatically) all the steps involved in the heap sort on the following input sequence: 18, 45, 9, 2, 21, 64, 4, 7, 1, 6. You should sort the sequence in the increasing order.
b) Repeat part a) if the heap sort is performed in place.
Q4. Answer the following questions:
a) Bill suggested that he can implement a queue ADT using a priority queue. Recall that a queue supports enqueue and dequeue operations, while a priority queue supports min(), removeMin and insert operations. Explain how Bill can achieve this by showing the necessary pseudo code for implementing the queue ADT.
b) Referring to a) above, what are the tight big-Oh time complexities of the enqueue and dequeue operations of the newly designed queue given that the priority queue is implemented using a heap? Explain your answer

Answer 1

Heap sort is carried out by creating a max heap, repeatedly removing the maximum element to the end of the list, and heapifying the remaining elements. When implemented in-place, no additional heap is created; the array itself is modified. Queue ADT can be implemented with a priority queue by associating insertion order with each element, with both enqueue and dequeue operations having an O(log n) time complexity.

Step-by-step explanation:

Heap Sort Explanation

Heap sort is a comparison-based sorting technique based on a binary heap data structure. It's similar to selection sort where we find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

a) Heap Sort Steps Diagrammatically

The given sequence is: 18, 45, 9, 2, 21, 64, 4, 7, 1, 6

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 the size of the heap is greater than 1.

b) In-Place Heap Sort

Performing heap sort in-place means sorting the array without using extra space for another heap data structure. The steps described above are applied directly to the input array, and space is typically saved by using an index to keep track of the "end" of the sorted elements.

Queue ADT Implementation Using Priority Queue

a) Pseudo Code

To implement a queue using a priority queue, each element must have an associated priority that determines the order in which elements are dequeed. The priority can be taken as the insertion order.

class PriorityQueueBasedQueue {
int order = 0;
priority_queue pq;

void enqueue(value) {
pq.insert(value, order);
order++;
}

void dequeue() {
return pq.removeMin();
}
}

b) Time Complexity of Operations

The enqueue operation has a time complexity of O(log n), because it involves inserting a new element into the priority queue, which is a heap, and thus requires heapifying the elements. The dequeue operation also has a time complexity of O(log n), as it requires the removal of the minimum element, which also involves heapifying the elements.