Menu
I have a vector that I want to use to create a heap. I'm not sure if I should use the C++ make_heap function or put my vector in a priority queue? Which is better in terms of performance? When should I use one vs. the other?
769
Operating Systems: Priority queues are used to select the next process to run, ensuring high-priority tasks run before low-priority ones. It is also applied for load balancing, and interrupt handling.
The priority queue only offers access to the largest element, while the set gives you a complete ordering of all elements. This weaker interface means that implementations may be more efficient (e.g. you can store the actual queue data in a vector , which may have better performance on account of its memory locality).
The priority queue (also known as the fringe) is used to keep track of unexplored routes, the one for which a lower bound on the total path length is smallest is given highest priority. Heap Sort : Heap sort is typically implemented using Heap which is an implementation of Priority Queue.
The priority queue is working on the queue and the heap is working on the tree data structure. The priority queue is stored array value in a simple form while the heap is stored array value in a sorted form. The heap provides multiple functions and operations than the priority queue.
There's no difference in terms of performance. std::priority_queue is just an adapter class that wraps the container and the very same heap-related function calls into a class. The specification of the std::priority_queue openly states that.
By building a heap from an exposed std::vector and calling heap-related functions directly, you keep it open to the possibility of outside access, potentially damaging the integrity of the heap/queue. std::priority_queue acts as a barrier restricting that access to a "canonical" minimum: push(), pop(), top() etc. You can see it as self-discipline enforcing measure.
Also, by adapting your queue interface to the "canonical" set of operations, you make it uniform and interchangeable with other class-based implementations of priority queues that conform to the same external specification.
101
A priority_queue is (at least normally) implemented as a heap. As such, the real question is whether a priority_queue provides what you need. When you use make_heap you still have access to all elements. When you use priority_queue, you have only a few operations giving very limited access to elements (basically just insert an item, and remove the item at the head of the queue).
29
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
