Priority queue

**cjwenigma** · 12-01-2007

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

**iMalc** · 12-01-2007

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.

**cjwenigma** · 12-02-2007

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

**CornedBee** · 12-02-2007

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.

**cjwenigma** · 12-03-2007

Originally Posted by iMalc

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)??

**iMalc** · 12-03-2007

Originally Posted by cjwenigma

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.

**cjwenigma** · 12-03-2007

Sorry, I'm just having a hard time understanding asymptotic notation. I'll figure it out..... thanks for trying to help me.

Thread: Priority queue

Thread Tools

Search Thread

Display

Priority queue

Similar Threads

Help with FIFO QUEUE

Fixing my program

Priority Queue Help

help with queues

help with queues