1)Assume the priority queue also must support the update DELETE(A,i), where i gives you the location in the data strucure where element i is located. In a binary heap, that would be A[i]. Write pseudocode to achieve DELETE(A,i) in O(log n) time for binary heaps, where n is the size of the heap.

Justify the running time.

2)Give an algorithm with worst-case running time of O(k log k) to print the k biggest elements in a n-element max-heap (binary heap stored in an array) without modifying the max-heap (or if you do modify it, restore it to the input heap within the given time bound). For example, if the max-heap is A = [100, 88, 44, 66, 77, 11, 22, 5, 55] and k = 5, the output could be 100, 88, 66, 77, 55 (the order in which the algorithm prints does not matter). Do not assume n = O(k). Here n can be much larger than k.

A correctness proof is not needed (but your pseudocode must be correct). You can use additional data structures. Argue the running time.

Answered it.Hope I get a Helpful rating from you.

Step-by-step explanation

1.For a delete operation, we need to define some helper methods and follow the below steps

1. For element at A[i] change its priority to some large value (larger than the current maximum) ->This takes O(1)time
2. Then shift that A[i] up, so as to maintain the heap property -> This will take O(log n) time
3. Now extract it and remove it using getMax() -> takes O(1) time
4. Finally, heapify the structure again -> takes O(log n) time

So in total time complexity is O(1) + O(log n) + O(log n) + O(1)
which is equivalent to O(log n)

2.Solution

Let a be the array in which elements of the max heap are stored.

Number of nodes in a binary tree of height h = 2^h+1-1

We know that in the case of the max heap the k largest elements exist between the root and the maximum height k-1 in the binary max heap.

Number of nodes in the binary tree of height k-1 = 2^h+1-1 = 2^k-1+1-1 = 2^k - 1

So the k largest elements exist among the front  2^k - 1 elements in the array.

So we can search the array from index 0 to index  2^k - 2.

The required algorithm is shown below:

get_k_Biggest_Elements(Array_a)

integer m =  2^k - 1??????

Create a new array b of size m.

The elements from index 0 to index 2^k - 2 in array a are copied to array b.

  BUILD-MAX-HEAP(b)

  for i:= 1 to k

Heap-Extract-Max(b)

  MAX-HEAPIFY //This step results in O(log k) complexity

end for

Explanation And Complexity Analysis:

Construct a new max-heap using the front 2^k - 1???????element from the given array(which is a max heap)

Note the height of the new max heap is k.

The maximum element is present in the root node.

We extract the maximum element from the heap and convert it back to the max heap. This step has a complexity O(log k).

Since the previous step is performed k times, hence total time complexity = k *  O(log k) =  O(klogk)