GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
114 views

asked in Algorithms by Active (1.4k points)   | 114 views

2 Answers

+4 votes
Best answer

a) Priority queue is implemented efficiently .For minheap we can say priority of a node is inversely proportional to the weight of a node and similarly for maxheap priority is directly proportional to the weight of a node..

And we know deletion and insertion operation in binary heap(min heap or max heap) takes  O(logn) time..Hence it is an efficient data structure for priority queue implementation assuming almost equal number of insertion and deletion occurs.

If say no of insertion operation is much higher than no of deletion , then unsorted array would be the best data structure for priority queue implementation since insertion in unsorted array does not require finding the appropriate place for insertion hence it will take O(1) time for insertion.

 

b) Maxheap  can  be used efficiently to find kth minimum..Let us see how..Let we have n elements.

 Steps :

1) Build a Max-Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)

2) For each element, after the k’th element (arr[k] to arr[n-1]), compare it with root of MH.
……a) If the element is less than the root then make it root and call heapify for MH
……b) Else ignore it.
// The step 2 is O((n-k)*logk)

3) Finally, root of the MH is the kth smallest element.

Time complexity of this solution is O(k + (n-k)*Logk)

In this way we can use the maxheap data structure easily to find kth minimum

Reference : http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

Hence option C should be the correct option.

answered by Veteran (66.5k points)  
selected by
+1 vote
I think both i and ii

to find kth largest and smallest element from an array we can do:

sort the array which takes O(nlogn) time and find the largest/smallest: TC= O(nlogn)

Build the max heap and extract largest element : O(n) + O(1) = O(n) time

Build the min heap and extract the smallest element : O(n) + O(1) = O(n) time
answered by Boss (8.4k points)  


Top Users May 2017
  1. akash.dinkar12

    3152 Points

  2. pawan kumarln

    1616 Points

  3. sh!va

    1580 Points

  4. Arjun

    1336 Points

  5. Devshree Dubey

    1230 Points

  6. Angkit

    1028 Points

  7. Debashish Deka

    1012 Points

  8. Bikram

    972 Points

  9. LeenSharma

    810 Points

  10. srestha

    662 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    242 Points

  2. Ahwan

    138 Points

  3. joshi_nitish

    112 Points

  4. jjayantamahata

    104 Points

  5. Arjun

    64 Points


22,725 questions
29,056 answers
65,053 comments
27,566 users