Thread: Priority Queues

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    17

    Priority Queues

    Anyone have any good reading material on priority queues? I don't have the foggiest idea how to create one please help.

    -DeeMan

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    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.

  3. #3
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    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.

  4. #4
    Registered User
    Join Date
    Feb 2013
    Posts
    17
    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.

  5. #5
    Registered User
    Join Date
    Nov 2011
    Location
    Saratoga, California, USA
    Posts
    334
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Priority queues
    By sigur47 in forum C++ Programming
    Replies: 1
    Last Post: 02-07-2012, 07:22 PM
  2. Priority Queues
    By Korhedron in forum C++ Programming
    Replies: 10
    Last Post: 07-20-2010, 10:32 AM
  3. Applications of priority queues
    By C_Enthusiast in forum C Programming
    Replies: 2
    Last Post: 06-21-2010, 09:07 AM
  4. Priority
    By siavoshkc in forum Windows Programming
    Replies: 1
    Last Post: 01-18-2006, 01:57 AM
  5. BST implementation of priority queues
    By jcleong in forum C Programming
    Replies: 1
    Last Post: 05-14-2002, 09:09 AM