   Priority queue
  I want to convert this queue class in a priority queue class, I have seeking in internet, but the examples I see are all complicated (for me), I want the easiest method to implement a pqueue based in this code. I don''t know anything about containers, comparable objects, ... but the name , this things are hard to me.Basically, the insert and remove methods is what i need to change to make a pqueue, can anyone explain me in easy mode how to do it?   class Queue {final static int DEFAULT = 10;Object array[];int MaxSize;int index;Queue() {MaxSize = DEFAULT;index = 0;data = new Object[MaxSize];}Queue(int size){MaxSize = size;index = 0;array = new Object[MaxSize];if (array == null)return;}void insert(Object element) {if (index == MaxSize)return;array[index] = element;index++;}void remove() {for (int i=0;i<MaxSize - 1;i++)array[i] = array[i+1];index--;}Object front() {return array[0];}Object back() {if (index == 0)return null;return array[index-1];}boolean isEmpty() {return (index == 0);}boolean isFull() {return (index == MaxSize);}}
  Well, here's how a priority queue works.  You have an array.  In this case, lets leave array[0] empty.A priority queue can be drawn as at tree, where the left child of array[x] is array[2*x] and the right child is array[2*x+1].  If you start drawing some sample priority queues, you'll see how this works.I'm going to assume you want the largest value at the top of the queue.For inserting, you place the number at the very end of the array.  Then you compare it, assuming it's at array[x], to its parent array[x/2].  If its parent is greater, you swap them.  You keep doing this until the parent is greater.To remove something, you remove it, and insert the last element in the array to the empty slot.  Now, you compare this element you just inserted to its children.  If either of its children are greater, swap the greater of the two with the element you just inserted.  Continue doing this until you have a valid priority queue.   [edited by - nickwinters on July 31, 2003 4:23:42 PM];  Is this different from a min/max heap? ;  its better make a priority queue or make a sorted insert, if is sorted insert, how can I do it? (in begining vector are empty) ;quote:Original post by Geoff the Medio  Is this different from a min/max heap?   What nickwinters described was a max heap. It''s the most common way to implement a priority queue.   AnkhSVN - A Visual Studio .NET Addin for the Subversion version control system. ;  I have problems in remove function, how to test if a binary heap is a valid binary heap? what are the conditions? ;quote:Original post by Anonymous Poster  I have problems in remove function, how to test if a binary heap is a valid binary heap? what are the conditions?   From http://www.nist.gov/dads/HTML/binaryheap.html:quote:binary heap(data structure)Definition: A complete binary tree where every node has a key more extreme (greater or less) than or equal to the key of its parent.Your binary heap will be valid if you insert and remove your values the right way. It hope this helps you.;  I have made the insert and remove methods with the explaining of nickwinters, now how I can know if the array that I obtain, is a valid binary heap and there arent bugs/errors ? what conditions are to know this ;  the binary heap works good with floats/doubles? because I have inserted in this order 0.5/0.2/0.1/0.01/2.2/1.2 and the result I get poping the values is: 0.1/0.01/0.2/0.5/2.2/1.2  0.1 > 0.01!! 2.2>1.2!! I have do it manually (pencil and paper) and with programming, but I get the same result 