Understanding PriorityQueue: A Code Snippet Guide

[TenNen]

Can you give me a code snip clearifying some basic uses of PriorityQueue ?
I read Bjarn but wasn't clear enough, could you please help me ?
Thanks in advance,

 

[Goalie_Ca]

This is all you need to know:

FIRST IN = FIRST OUT.

There are three main operations, queue, dequeue, and peek. dequeue removes first element, queue adds item to end of list, peek retrieves first item but doesn't remove.

It would be used in cases where you have a bunch of messages or items that need to be accessed in that order. So like if you had a lineup in a store, you would queue people up, and dequeue them in order. In an operating a message loop might be used. As messages arrive they are put on the queue and the program takes one off every loop.;

 

[chroot]

Goalie: A simple queue is quite different from a priority queue.

http://www.nist.gov/dads/HTML/priorityque.html

- Warren

 

[TenNen]

Goalie: A simple queue is quite different from a priority queue.

http://www.nist.gov/dads/HTML/priorityque.html

- Warren

Thanks Warren,

 

[TenNen]

This is all you need to know:

FIRST IN = FIRST OUT.

There are three main operations, queue, dequeue, and peek. dequeue removes first element, queue adds item to end of list, peek retrieves first item but doesn't remove.

It would be used in cases where you have a bunch of messages or items that need to be accessed in that order. So like if you had a lineup in a store, you would queue people up, and dequeue them in order. In an operating a message loop might be used. As messages arrive they are put on the queue and the program takes one off every loop.;

Goalie_Ca,
I have tried to search the net but I haven't found anything like examples to test on my compilers, I didn't know about peek either, thanks for your information.
Could you please write me an example using priority_queue ? If Philips were here, he sure would be able to give more examples.
Come on Goal-Ca write it please, I would like to learn a little...true, thanks a lot in advance

 

[Goalie_Ca]

lol, ya, i got the terms mixed up... but I'm not the only one. I've seen priority queue used to describe that priority is given to first in.

TenNen, firstly can you write a simple queue? (or a linked list?, reference or array based?) From there you simply add a priority variable to each node and change the behaviour of insertion and deletion to accommodate. You can also add other functions.

Here's the c++ STL implementation. Play around with this first, then if you get comfortable write your own (write a linked list first if you don't know how!)
http://www.sgi.com/tech/stl/priority_queue.html

 

[dduardo]

TenNen, I'm guessing you want to know about the binary heap priority queue? To implement it you'll need to know a few things.

1. A heap is a binary tree using an array instead of pointers. Each parent should have a maximum number of children. In my example I willl show you a heap that has two children per parent.

Heap: [1,3,5,6,7,8,9] =

Binary Tree:

        1
       /  \
     3     5
   /   \    / \
  6    7  8  9

Position 0 in the array is the root of the tree. If a parent node is located at X, then the children nodes are located at 2X+1 and 2X+2.

2. Insertion: O(log n) When you insert a number, you first check to see if the queue is full (You haven't exceded the limited size of your array). If your queue isn't full, you want to add the next number in the array. You'll need to keep track of the last index so you know where to place the next node in the array. (Start) After that you want to check if the parent has a larger priority than child node you just inserted. If the child has lower priority than the parent than your done. If not, then you need to check the index. If the index is odd (starting from 0) then you know where the parent is located based on the 2X+1. If the index is even then you know where the parent is located based on the 2X+2. You will then swap the child for the parent. Now you want to go back to the (Start) I placed in this paragraph, and repeat the same check on the new parent.

Example: Insert 2 in the example heap

Step 1
Heap: [1,3,5,6,7,8,9,2] =

Binary Tree:

        1
       /  \
     3     5
   /   \    / \
  6    7  8  9
  /
2

Step 2
Heap: [1,3,5,2,7,8,9,6] =

Binary Tree:

        1
       /  \
     3     5
   /   \    / \
  2    7  8  9
  /
6

Step 3
Heap: [1,2,5,3,7,8,9,6] =

Binary Tree:

        1
       /  \
     2     5
   /   \    / \
  3    7  8  9
  /
6

3. Deletion: O(log n) When you pop off the highest priority you take the last element in the array and move it to the root of the tree (element 0 in the array). You'll then need to heap sort the heap.

Pop Highest Priority Element
Heap: [6,2,5,3,7,8,9] =

Binary Tree:

        6
       /  \
     2     5
   /   \    / \
  3    7  8  9

Heap Sort: O(n log n)

#include<iostream>

using namespace std;

void shift_down(int heap[], int top, int bottom) {

bool finished = false;
int temp, max ;

while( (top*2 <= bottom) && !finished ) {

        if ( top*2 == bottom ) {
                max = top * 2 ;
        } else if ( heap[top * 2] > heap[top * 2 + 1] ) {
                max = top * 2 ;
        } else {
                max = top * 2 + 1 ;
        }

        if( heap[top] < heap[max] ) {
                temp = heap[top] ;
                heap[top] = heap[max] ;
                heap[max] = temp ;
                top = max ;
        } else {
                finished = true ;
        }
}}

void heap_sort( int heap[] , int heap_size ) {

int temp ;

for( int index = (heap_size / 2)-1 ; index >= 0 ; index-- ) {
        shift_down(heap, index, heap_size) ;
}

for( int index = heap_size-1 ; index >= 1 ; index-- ) {
        temp = heap[0] ;
        heap[0] = heap[index] ;
        heap[index] = temp ;
        shift_down(heap, 0, index-1) ;
}}

int main( int argc, char *argv[] ) {

int heap[7] = {6,2,5,3,7,8,9};

for( int index = 0 ; index < 6 ; index++ ) {
        cout << heap[index];
}

cout << endl;

heap_sort(heap , 7);

for( int index = 0 ; index < 6 ; index++ ) {
        cout << heap[index];
}

cout << endl;

return 0;

}

Here is the code for heap sort. It will sort my example and print out the results (before and after). I encourage you to take the time to examine it and figure out how it works. This is a pretty standard algorithm. If you want the detailed explantion of how heap sort works or have any additional questions please ask.

 

[TenNen]

lol, ya, i got the terms mixed up... but I'm not the only one. I've seen priority queue used to describe that priority is given to first in.

TenNen, firstly can you write a simple queue? (or a linked list?, reference or array based?) From there you simply add a priority variable to each node and change the behaviour of insertion and deletion to accommodate. You can also add other functions.

Here's the c++ STL implementation. Play around with this first, then if you get comfortable write your own (write a linked list first if you don't know how!)
http://www.sgi.com/tech/stl/priority_queue.html

lol,
Okay, I am sorry too,
Thanks for your help, lol

 

[TenNen]

dduardo, that's really nice of you, Thanks a lot,