Anyone have any good reading material on priority queues? I don't have the foggiest idea how to create one please help.
-DeeMan
Anyone have any good reading material on priority queues? I don't have the foggiest idea how to create one please help.
-DeeMan
Wikipedia is always a good place to start: Priority queue - Wikipedia, the free encyclopedia. The typical implementation is a heap though many other possibilities exist, like a binary search tree, or even an array or linked list (though the performance is often inferior). I suggest you read up on heaps: Heap (data structure) - Wikipedia, the free encyclopedia.
Note that a priority queue is more about the order you process elements, not how it's implemented. This difference is similar to the difference between linked lists and queues, like in your thread from last week: FIFO queue vs Link List
A FIFO queue is about the order you process/remove elements. So is a priority queue.
A linked list is about how you store those elements internally. So is a heap.
One other thing to keep in mind is whether you need sort stability. What this means is, if you introduce several elements of equal priority, is it important that you get them back in the order of insert (i.e. in the case of a tie in priority, must the element inserted first be returned first)? That can factor into whether you use a heap (or how you implement the heap). A run of the mill heap is not stable; you will get one of the highest priority items but you don't necessarily get them in any particular order.
A self-balancing binary tree can be used as well as a heap - more complex to implement but you can gain sort stability.
You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.
Thanks anduril462 cat cat for your responses. I need to implement a heap, and I have to heap sort the element that are put in it. I have read through the Wikipedia site, and I will try my luck. This seem difficult, but I will try and post my code.
A couple of Google hits to help you :
Binary heap - Wikipedia, the free encyclopedia
Build Heap
I would implement as array unless there was a good reason not to.
Understand the parent-child relation and how relative positions are calculated. Then the fact that the root is either the largest (max heap) or least (min heap) value. The two basic operations are to remove the root and to add a new node in the next empty leaf. The operations that follow those are to repair the heap.
Good luck.