1 Replies - 1671 Views - Last Post: 03 August 2011 - 07:00 AM Rate Topic: -----

#1 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Insert method in Priority Queue

Posted 03 August 2011 - 01:05 AM

I was just reading the following insert method for priority queue and found it confusing.

Here's the method:

public void insert(double item) // insert item
{
int j;
if(nItems==0) // if no items,
queArray[nItems++] = item; // insert at 0
else // if any items,
{
for(j=nItems-1; j>=0; j--) // start at end,
{
if( item > queArray[j] ) // if new item
larger,
queArray[j+1] = queArray[j]; // shift upward
else // if smaller,
break; // done shifting
} // end for
queArray[j+1] = item; // insert it
nItems++;
} // end else (nItems > 0)
} // end insert()
//-------------------------------------------------------------



Let me tell you whats confusing for me. Lets say we only 1 data in our array. lets say 30. Now, we want to insert 40 in our array. So, according to the method, since we have only one data, we will loop only once. Our item = 40 and queArray[j] = 30. Since item is greater than queArray[j], 30 will now be stored at queArray[j+1]. Now here's where the confusion lies. Once we move outside the loop, queArray[j+1] is initialized to item while a moment ago,it was initialized to queArray[j], which is 30. How does this make sense that one memory location consist of two data?

I'll appreciate your inputs.

Is This A Good Question/Topic? 0
  • +

Replies To: Insert method in Priority Queue

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10766
  • View blog
  • Posts: 40,087
  • Joined: 27-December 08

Re: Insert method in Priority Queue

Posted 03 August 2011 - 07:00 AM

This is just insertion sort. What happens is you have a group of elements. Say: [0,3,4,8,9] and you insert 7. What happens is that 9 is shifted down one space, followed by 8. So we now have [0,3,4,8,8,9]. B/c 8 was originally next to 4, and we've already transferred that value down one space, we can overwrite that first 8 with a 7. So the array now becomes [0,3,4,7,8,9]. No element holds two values at once.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1