Thread: Priority Queue Help

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    46

    Priority Queue Help

    Here is my priority queue.. I can't seem to get my enqueue and dequeue to work quite right. The enqueue will work to a certain extent but still isn't that great. Any suggestions?

    Code:
    #include<iostream>
    using namespace std;
    
    const int MAX = 10;
    const int DUMMY_PRIORITY = 1000;
    class qNode {
    public:
      int num;      // queue element
      int priority; // queue priority
      qNode();
      ~qNode();
    };
    
    qNode::qNode() {
      num = 0;
      priority = DUMMY_PRIORITY;
    }
    
    qNode::~qNode() {
    }
    
    class queue {
    private:
      qNode q[MAX]; // queue node
      int size;    // queue size
    public:
      queue();
      ~queue();
      bool isEmpty();
      bool isFull();
      void enqueue(int,int);
      int dequeue();
      void show();
    };
    
    queue::queue() {
      size  = 0;
    }
    
    queue::~queue() {
    }
    
    bool queue::isEmpty() {
      bool empty = false;
      if(size == 0) {
        empty = true;
      }
    
      return empty;
    }
    
    bool queue::isFull() {
      bool full = false;
      if(size == MAX) {
        full = true;
      }
    
      return full;
    }
    
    void queue::enqueue(int number, int priority) {
      bool placedElement = false; // determine whether or not the element was placed
      qNode tempNode1;
      qNode tempNode2;
      int temp = 0;
      
      /* if the queue is empty, just add the number to the front of the queue */
      if (isEmpty()) {
        q[temp].num = number;
        q[temp].priority = priority;
        size++;
        placedElement = true;
      }
      else {
        while (!placedElement) {
          if(q[temp].priority > priority) {
    	if(q[temp].priority != DUMMY_PRIORITY) {
    	  tempNode1 = q[temp];
    	  q[temp].num = number;
    	  q[temp].priority = priority;
    	  size++;
    	  for(int i = temp + 1 ; i <= size ; i++) { // move the elements up
    	    tempNode2 = q[i];
    	    q[i] = tempNode1;
    	    tempNode1 = tempNode2;
    	  }
    	}
    	else {
    	  q[temp].num = number;
    	  q[temp].priority = priority;
    	  size++;
    	}
    	placedElement = true;
          }
          else {
    	temp++;
          }
        }
      }
    }
    
    int queue::dequeue() {
      int element = q[0].num;
      qNode tempNode1;
      qNode tempNode2;
      
      if(!isEmpty()) {
        size--;
        tempNode1 = q[size-1];
        for(int i=size-1; i > 0; i--) {
          tempNode2 = q[i-1];
          q[i-1] = tempNode1;
          tempNode1 = tempNode2;
        }
      }
    
      return element;
    }
        
    
    void queue::show() {
      for(int i=0; i<MAX; i++) {
        cout << "Element -> " << q[i].num << "\t" << "Priority -> " << q[i].priority << endl;
      }
    }
    
    int main() {
      int num;
      int priority;
      
      queue myQueue;
      for(int i=0; i<MAX; i++) {
        cout << "enter a number -> ";
        cin  >> num;
        cout << "enter a priority -> ";
        cin >> priority;
        myQueue.enqueue(num,priority);
        cout << endl << endl;
        myQueue.show();
        cout << endl << endl;
      }
    
      // dequeue 3 elements
      cout << "dequeuing " << myQueue.dequeue() << endl << endl;
      cout << "dequeuing " << myQueue.dequeue() << endl << endl;
      cout << "dequeuing " << myQueue.dequeue() << endl << endl;
    
      // myQueue.show();
      return 0;
    }

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    What would you like to improve about it?

    Other suggestions:
    isEmpty could be implemented much more nicely:
    Code:
    bool queue::isEmpty() {
      return size == 0; //or !size
    }
    Same thing about isFull.

    A larger change might be to store the nodes in reverse, those with highest priority coming last. This should make dequeuing trivial (decrement size).

    To insert, start to loop backwards from size-1 while the current element has higher priority, moving it up one position in the array, until you find the right place to insert the current node.

    When you print out the queue, may-be you shouldn't print the unused nodes (you shouldn't care what their value is).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    That's a very poor priority queue I'm afraid. It's O(n) insertion and removal.
    You should be using a heap which is O(log n) insertion and removal.
    As such I'm not going to offer any suggestions on little fixes to that code. You need to start again using a heap.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I assume this is just a school assignment and the OP is just learning about classes. Therefore the efficiency of the container type should not be a concern.

    Writing a container seems to be a good way to learn about classes because there are so many ways it can be implemented. If the implementation is well hidden from the user of the class, you can change it any way you like without having to change the code that uses this class.

    Speaking of which I would make MAX a private static constant inside queue, not a global, and change this loop
    Code:
    for(int i=0; i<MAX; i++)
    into
    Code:
    while (!myQueue.isFull())
    The reason is that the size of the underlying container is an implementation detail that the rest of the code shouldn't know about. If you indeed decided to use a heap or something different that would give you the possibility to store unlimited number of nodes, MAX would become meaningless but code outside the queue is still expecting it to mean something. (Of course, isFull would become rather meaningless too .)
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I'm unphased as to whether it is an assignment or not.
    But if it is, and I suspect that is, considering it is all in one file, then they have been asked to implement a priority queue, and in that case you can be damn sure it was intended to be implemented using a heap, so this submission would be wrong.
    "Priority queue" is pretty much synonymous with "Heap".
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Wikipedia doesn't seem to agree. A heap is a good way to implement it, but what makes something into a priority queue is what it allows you to do: to insert things and retrieve things in the order of priority. It also mentions that if it is implemented using an ordered array as OP is doing, then the relevant sort routine (for inserting thing) is insertion sort.

    Considering that with an ordered array you should be able to get O(n) insertion, O(1) top and O(1) pop, a queue of only 10 elements might even be more efficient this way. (If the size limitation is dropped, the class design should allow to change to more efficient representation without any significant changes to user code.)

    If OP is still wondering how to improve things, then you should drop the arbitrary DUMMY_PRIORITY. Because you should be able to know how many nodes the queue actually contains, you just shouldn't ever look at the unused ones - which therefore might just as well contain garbage.

    ----------

    It took me long to reply because this heap thing is new to me too and I spent quite some time implementing a priority queue and reinventing std:: push_heap and std:: pop_heap. So at least I learnt something new
    Last edited by anon; 11-14-2007 at 05:36 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Wikipedia doesn't disagree with me. A heap is the most general and most efficient, and hence most common method of implementing a Priority queue. In fact it's hard to find anyone that doesn't automatically assume you mean a heap when you say priority queue.

    Where it says "for integer data faster implementations exist", I am familiar with a van Emde Boas tree. It's very very complicated, uses a ton of memory, and is only faster if you have a massive number of items. I've been hunting for an implementation of a van Emde Boas tree before after barely managing to understand them, and found none. Don't be mislead, in the real world people use a heap.

    I'm surprised there are even programmers out there that don't know all about heaps already. It's one of the fundamental data structures that I thought everyone gets taught, and it's hard to remember ever not knowing it. As a matter of fact, my Avatar is a picture of heapsort in action! (I made an animated gif of it, but they wont let us pleb users use gifs)
    Now if you didn't know what a "Beap" was you could be forgiven...

    Oh and yes I too would simply use an ordered array for a priority queue that was a always maximum of about 8 items.
    Last edited by iMalc; 11-15-2007 at 12:54 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  3. Priority Queue Question
    By ac251404 in forum C++ Programming
    Replies: 26
    Last Post: 08-16-2006, 11:51 AM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM