Heap - Please explain first statement

Question

33. Which of the following statements about max heap are true ?
(I) To find the kth largest element in the heap, the time required is $\mathrm{O}(\mathrm{klogn})$, where k is less than the number of element in the heap.
(II) To find the kth smallest element in the heap , the time required is $\mathrm{O}(\mathrm{n})$, where k is less than the number of element in the heap.
(III) Given a pointer to the an element in the heap, if we want to delete the element, and restore back the heap property then we require $\mathrm{O}(\log n)$ time.
( Marks: -0.66 )

• A. $\quad \checkmark$ All are correct
  
  Explanation:
  All given statements are correct.
  (I) Since, the given heap is a max heap, the root always holds the maximum value. To find the kth largest number in the array we, can perform k-1 heapify operations, and then find the element at the root of the heap. The element at the root of the heap now is the kth largest element.
  (II) Since the given heap is a max heap, hence the smaller element has a great chance of being at the last level in the heap. Since the number of heaps in the last level is $O(n / 2)=O(n)$, therefore we require $\mathrm{O}(\mathrm{n})$ search operations to find the kth smallest number in the heap.
  (III) The question asks that given an index of the heap, to remove that element from the heap, we require O(logn) time. This statement is correct. Suppose we are given the index, then we perform increase key operation on the index of the heap. We, increase the value in that index of the heap to infinity ( a practically high value) and perform heapify on that index. Now, this value comes to the root of the heap. Now, we perform extract min operation on the heap. In , this way we can delete an element from heap, given a pointer to the node.
  
  Hence, all the statements are correct.
  
• B. $\times \times$ Only (II) and (III) are correct.
  
• C. X Only (I) and (III) are correct.
  
• D. X Only (I) and (II) are correct.

Comments

Useful read for 1st statement

https://stackoverflow.com/questions/5380568/algorithm-to-find-k-smallest-numbers-in-array-of-n-items

Answer 1

yes all are correct!

In first case to find the kth largest element, do k-1 deletions from the max heap, so k-1 times max-heapify procedure will be called.

T.C (k-1)logn = O(klogn)

Comments

Option (ii) is also okay as K is less than number of element

---

@Sandeep Suri

please read above comments first.

---

It's looking for a minimum element in a MAX Heap. Why are you deleting the items here and heapifying again?

In any case it should take maximum O(n) T.C