hi

im trying to write some code for a priority queue using an unsorted array..it should be easy but i have a few concerns about it..

say if i have a graph of something like this:

node 0, priority 100
node 1, priority 50
node 2, priority 200
node 3, priority 250

then the array would look something like

pq[0] = 100
pq[1] = 50
pq[2] = 200
pq[3] = 250

so far so good..the index of the array corresponds to the node number and the value corresponds to the priority...
but what if i was to do a delete min operation? the array would look something like

pq[0] = 100
pq[1] = 200
pq [2] = 250

i deleted the element with lowest priority and shifted everything down to fit the array..but the problem is now pq[1] = 200, which would mean that the node number 1 has a priority of 200 however this is not the case? node 1 just got deleted, the node with priotiy 200 is node 2...

i was thinking maybe implement it using 2 arrays, 1 for storing the node numbers and the other for storing the priorities..but then again that might be doing too much

any help would be appreciated. thanks.

Your program is using the array subscript to serve as a node which is the problem. Even though you removed the data, the second subscript, pq[1], isn't going to change.

Have you tried doing it with a linked list?

no i have not, i was simply wondering if it was possible to do it with an array. I have sort of got a work around by setting the value of the priority to -1 when you try to do delete it. this way the index still corresponds to the correct node and as there are no negative priorities, the next delete min would just check for the node with lowest priority that is >0. is this ok?