Priority queue

This is a discussion on Priority queue within the C++ Programming forums, part of the General Programming Boards category; Let's say I had a priority queue, Q, I'm trying to write an alogorithm that will implement the enqueue operation. ...

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

    Priority queue

    Let's say I had a priority queue, Q, I'm trying to write an alogorithm that will implement the enqueue operation.

    here is my enqueue...

    Code:
    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++;
          }
        }
      }
    }

    Also if I used Asymptotic notation, what would be the worst case time complextiy of this operation? Any ideas..?

    Thanks

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    That looks pretty complicated. I'd expect such a function to only be about 6-10 lines long when using a simple ordered array.
    Given any thought to using a heap instead?

    If you have n items, how many items do you have to move when the new item you enqueue is smaller than all of them? There's your answer.
    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"

  3. #3
    Registered User
    Join Date
    Apr 2007
    Posts
    46
    I see what you mean sorta...I'm not that great at asymptotic notation

    I'm not sure how you figure out which one it is... This stuff is new to me.
    I do know some basics..

    O(1) “constant”
    O(log n) “logarithmic”
    o(n) “sublinear”
    O(n) “linear”
    O(n log n) “supralinear”
    O(n2) “quadratic”
    O(nc) “polynomial”
    O(cn) “exponential”
    O(n!) “factorial”


    If you any of you could explain this better..that'd be cool

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    The Big-O notation describes how some measurement of the algorithm's performance - speed, memory consumption, number of specific operations, etc. - varies with the number of elements in the operation, usually designated n.

    An O(1) operation is constant: the measurement is the same no matter how many elements there are. Access time for an array is O(1): it's just a pointer addition and a dereference, no matter how much you add to the pointer.

    An O(n) operation is linear: the measurement rises as a linear function of the number of elements. Searching a container without special properties for some element is O(n): you have to look at every element in turn to find the one that has the property you want. Worst case (the last one, or none at all, has the property) is that you have looked at all n elements.

    Note that Big-O notation discards linear scaling and constant factors. I.e. if for some operation you have to run through a sequence 10 times, that's still O(n), even though the number of element accesses is 10*n.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  5. #5
    Registered User
    Join Date
    Apr 2007
    Posts
    46
    Quote Originally Posted by iMalc View Post

    If you have n items, how many items do you have to move when the new item you enqueue is smaller than all of them? There's your answer.

    so would the time be constant? Big O(n)??

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Quote Originally Posted by cjwenigma View Post
    so would the time be constant? Big O(n)??
    You're making no attempt to even think about it; You just want the answer.

    Until you can answer my question, I wont be answering yours. Draw it on paper, step through the code, or actually just think about the question I asked. Whatever works.

    Lets try eliminating one answer shall we:
    Say we think it might be O(n!). First we'll pick n as 1.
    Okay I want to insert an item with priority of 1000 into an array that currently holds:
    (1500)
    If it were O(n!) then it would have to move at most 1 items. 1! = 1 moves. Yep, I would have to move that 1 item over to put 1000 in its place, giving (1000, 1500). So far so good.
    Now we'll pick n as 4.
    Okay I want to insert an item with priority of 1000 into an array that currently holds:
    (1500, 2000, 2500, 3000)
    If it were O(n!) then it would have to move at most 4! items. That's 4*3*2*1 = 24 moves which is more than the number of items we have, so that can't be right.
    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"

  7. #7
    Registered User
    Join Date
    Apr 2007
    Posts
    46
    Sorry, I'm just having a hard time understanding asymptotic notation. I'll figure it out..... thanks for trying to help me.

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, 02:55 AM
  3. Priority Queue Help
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 11-14-2007, 11:48 PM
  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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21