Priority queues
Good evening guys!
I would like to ask you sthg as far as priority queues are concerned.
When we want to add a new node in a priority queue,do we start checking the root first?Or do we add the node in a leaf node?
e.g. we have the tree
root->19
left child->20right child->40
l.c.->42l.c.->41r.c. ->45
and we want to add the number 12 ,where am i going to add it?
To the left subtree of 19 or to the right subtree of 19?
Thanks,in advance!
[562 byte] By [
g_p_javaa] at [2007-10-2 9:33:00]
This isn't a priority queue problem, it is a binary search tree problem. For a regular unbalanced search tree, the insertion algorithm is given in the following link about 1/3 down the page: http://www.cs.dartmouth.edu/~chepner/cs15/notes/08_bst.html
Good morning,
I use an array in order to implement a priority queue(i don't use the class Priority queue).
When we want to insert a number in the priority queue,do we use the shift up operation and when we want to delete a number from the priority queue we use the shift down operation?
Could anybody explain to me when in the tree we use the shift up or the shift down operation?
Thanks,in advance!
Yeah,you are right thank you!In the delete function i swap the root node with the last node and then i bubble down the root node which is now the last node.Is it right?Thanks,in advance?
Yes, you are correct that you move the last item in the array to the beginning of the array, then bubble down. Initially the parent (p) is index 0, and the children are:
c1 = 2 * p1 + 1, and
c2 = c1 + 1.
Always swap the smaller child (assuming a bottom heavy heap). The reason the smaller child is swapped is because the smaller child is smaller than the other child and the value that is being bubbled down, then the heap stays consistent. After the swap, the value of (p) is updated to be the index of the child that was swapped. If both children are larger then the bubble down stops.
