educative.io

Educative

Why we are not using priority_queue as minHeap here

Hi,

Can’t we use minHeap here? My logic is as below:

  1. insert into the minheap one by one.
  2. If minHeap size is greater than k, then pop().
  3. At last what we have inside the heap is top K largest elements.

Isn’t it better than using vector as minHeap? Am I missing anything here?

Thanks,
Souvik

2 Likes

The algorithm suggested will be faster with time Complexity of O(N logk) vs inserting everything in the priority queue -> O(NlogN) (iterate over each element and put in the right place in the priority queue).

@Rohan Wrong. According to the C++ documentation: https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue if you give the vector in as a parameter to the constructor, it will take O(N) to make the heap.

See also: https://stackoverflow.com/questions/44650882/time-complexity-of-a-priority-queue-in-c

So actually, the solution for this, with the same time complexity, is:

    vector<int> result;

    priority_queue<int, vector<int>> maxHeap(less<int>(), nums);

    for (int i = 0; i < k; ++i)

    {

      result.push_back(maxHeap.top());

      maxHeap.pop();

    }

    return result;

  }

2 Likes