Search code examples
c++priority-queue

C++ priority_queue

I am looking how to build a heap in O(n) time and I found it using Heapify. But I wonder whether the STL priority_queue do the same? So my question is:

Which method of build heap is used by priority_queue available in STL? Is it using the heapify which can turn the whole array to heap in O(n) or using one by one insertion of elements in heap taking O(n log n) time?

I am guessing it to be 2nd method as we manually insert elements one by one when using STL priority_queue. Am I correct?

Solution

  • There is std::make_heap(...), which accepts whole N-range at once to build heap.

    And as said in standard it has O(N) complexity. For example you can see how CLang implements std::make_heap, source is here.

    Later you can use std::push_heap and std::pop_heap for adding and taking-out 1 by 1 element if needed in O(log N) time.

    Also as suggested by @Jarod42 you can use just std::priority_queue, because one of its constructors accepts range (iterators) with N elements, this constructor has O(N) complexity too.