Skip to main content

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

8
  • Does the standard guarantee that make_heap will be cheap (logarithmic) in this special case? I also would like to avoid using a deque, I prefer vector for speed. (size of q will not increase over time). I would like to just put the new element at the front of the vector, and then sift it down until I have re-established the min-heap property. Maybe best to roll my own. Commented Feb 9, 2017 at 16:37
  • If I am remembering correctly, make_heap is the same algorithm that is used in priority queue. So, if you intend to use priority queue, there is no reason to avoid using make_heap. Commented Feb 9, 2017 at 16:45
  • But for a std::priority_queue, you often just call make_heap once at the beginning (expensive), then just pop and push elements often (push and pop are logarithmic). Commented Feb 9, 2017 at 16:47
  • I wanted to say that the cost of using pri queue is more than using make_heap. Commented Feb 9, 2017 at 16:58
  • Why? std pri q is just an adapter/wrapper over make_heap, push_heap and pop_heap. And the algorithmic complexity is as it should be in a heap. Commented Feb 9, 2017 at 17:12