in Algorithms
227 views
0 votes
0 votes

A ) 

B ) 

C ) 

D ) 

in Algorithms
227 views

6 Comments

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

> 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}

2
2

@amitraj123 They have given this explanation.

0
0

Subscribe to GO Classes for GATE CSE 2022

2 Answers

3 votes
3 votes

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).  

5 Comments

edited by

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.

1
1

> 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.

1
1
But are we allowed to modify the array’s contents?
1
1
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?
1
1
Yeah, I understand now, thanks!
0
0
0 votes
0 votes
Min Heap of Size of K. If size exeeds k, pop the top element out of Min heap