Chapter 7: Heaps and Priority Queues

Question 1

What will be the time complexity for deleting an arbitrary element from the min-heap?

Solution

To delete any element from the heap, we first have to search the element that is to be deleted, and then we delete the element.

Total time complexity = Time for searching the element + Deleting the element

= O(n) + O(log n)

= O(n)

Question 2

What will be the time complexity for finding the k^th smallest element from the min-heap?

Solution

The k^th element can be found out from the min-heap by performing delete operations k times. For each delete operation, the time complexity is O(logn). So, the total time complexity for finding out the k^th smallest element will be O(klogn).

Question 3

What will be the time complexity to make a max-heap that combines two max-heap each of size n?

Solution

O(n).

Since the time complexity of creating a heap from n elements is O(n), creating a heap of 2n...