3

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?

Improve this question
2
  • 1
    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. Commented Mar 24, 2021 at 11:32
  • 1
    The second method won't be O(N) in general, make_heap needs to be smarter than that to achive O(N) Commented Mar 24, 2021 at 11:37

1 Answer 1

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

And std::priority_queue uses std::make_heap when providing a range.
Thank you @Arty. So we can achieve it in O(N) but I still wonder if it uses heapify or something else for O(N)
@RitikaGupta In standard page it doesn't specify algorithm. It means that each compiler and platform is free to choose its own implementation as far as it is O(N). It can appear that some or even all compilers use heapify.
@RitikaGupta For example you can see how CLang implements it, source is here.
@Arty Thanks a lot.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.