227 views

A )

B )

C )

D )

max Heap  data structure of size n
No ans is D. I need  explanation for this one. How ans is D given.
Option A
What explanation they gave for option d?

> Use an array of size k as a min heap.
> With every element, compare it with min of heap, if found larger, insert in heap, else, ignore.
> Once the heap is full, if found larger than min of heap, delete the min and insert.

N = {8,4,2,6,1,5,6,9,10,3}, let k = 3 K = {}

N = {8,4,2,6,1,5,6,9,10,3} K ={8}

N = {8,4,2,6,1,5,6,9,10,3} K = {4,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {2,4,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {4,6,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {4,6,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {5,6,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {5,6,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {6,8,9}

N = {8,4,2,6,1,5,6,9,10,3} K = {8,9,10}

N = {8,4,2,6,1,5,6,9,10,3} K = {8,9,10}

@amitraj123 They have given this explanation.

### Subscribe to GO Classes for GATE CSE 2022

Answer will be max heap of size n.

We can access first max element from max heap in O(1).

After that just delete k max element from heap and after every delete heapify the tree make sure it is max heap, which will take O(logn).

So for K element time complexity will be O(klogn). And K is constant so O(logn).

edited

The Time Complexity should be at least $O(N)$ for scanning the items. If you’d only considered the $k$ sized heap then it should’ve been bound by terms of $k$, and $k$ here isn’t a constant, it might as well be $N$ for all it says.

Also, if I’m understanding correctly, you’re using a max heap. Finding $k$th maximum element(considering the max-heap element to replace when a better alternative is to be inserted) takes at least $k/2$ time(scanning leaves) since it can be present anywhere within the leaves. Time complexity would be $O(N.K)$ if it would be the case.

The Correct Option would be D using a min-heap and finding deleting min elements whenever we find a element greater than min-heap’s min thus finding max. Here, Time Complexity would be $O(N.\log k)$. Every time an element greater than min of heap is found, it takes $O(\log k)$ time to insert.

> Also, if I’m understanding correctly, you’re using a max heap. Finding kth maximum elements takes at least k/2 time(scanning leaves) since it can be present anywhere within the leaves.

I Believe what OP has done is created a max heap in time O(N), and then extracted K roots. i.e KLogN, the min-heap method should work in NLogK as we are scanning n elements and performing insertion/deletion in LogK time.

But are we allowed to modify the array’s contents?
But they can be copied right? Just take the n elements, copy them to an array, buildMaxHeap in O(N). I am not sure if I get your question correctly or maybe I am going wrong somewhere?
Yeah, I understand now, thanks!
Min Heap of Size of K. If size exeeds k, pop the top element out of Min heap