On Sat, Aug 19, 2000 at 01:01:37AM +1200, Chris, the Young One wrote:
> Wish I had enough brain cells to describe adequately what the functions
> do... I don't have Knuth's books in front of me either.
The lightbulb in my head suddenly flicks on, and I gain enlightenment...
I hope this is of use to others who want to understand prioq objects.
First, picture it as a structure that looks like this (the numbers are
the index numbers used in pq->p[]):
0
.---' `---.
1 2
/ \ / \
3 4 5 6
/ \ / \ / \ / \
7 8 9 10 11 12 13 14
Here, I refer to 0 as the parent of 1 and 2, who are the children of 0.
Likewise, 3 and 4 are the children of 1, who is the parent of 3 and 4.
The one guarantee that prioq_insert() and prioq_delmin() make is that if
an item has children, both of its children will have values greater than
that of the item. Similarly, its value will be greater than that of its
parent. Hence, pq->p[0], the parent of all parents if you will, always
has the smallest value.
i.e., assuming all items have unique values,
pq->p[0] < pq->p[1], pq->p[0] < pq->p[2],
pq->p[1] < pq->p[3], pq->p[1] < pq->p[4],
pq->p[2] < pq->p[5], pq->p[2] < pq->p[6],
and so on.
The descriptions that follow are not entirely accurate (since Dan's
functions are more optimal); I aim to make them easy to understand.
prioq_insert(): first, put new item at the next slot (15, if we use
the above diagram). Then, compare the value of the new item with that
of its parent (7 in this case). If parent has greater value, swap,
and see if the new item (now 7)'s parent (namely 3) is greater; keep
swapping until the new item is greater than its parent.
prioq_delmin(): swap the smallest item (at slot 0) with the child of
lesser value; keep swapping with the smallest item, until the item in
the final slot (14, if we use the above diagram) has a value less than
that of the item just swapped (or there are no more children to look
at). Then swap the smallest item with the item in the final slot, and
remove the final slot (effectively removing the smallest item).
Sorry, that was a mouthful. :-)
---Chris K.
--
Chris, the Young One |_ If you can't afford a backup system, you can't
Auckland, New Zealand |_ afford to have important data on your computer.
http://cloud9.hedgee.com/ |_ ---Tracy R. Reed
