PriorityQueue operates on a first-in, first-out principle, with three main operations: enqueue (adding an item), dequeue (removing the first item), and peek (retrieving the first item without removal). It is particularly useful for managing messages or items that need to be processed in a specific order, such as in a message loop. The discussion highlights the distinction between a simple queue and a priority queue, emphasizing the latter's ability to prioritize elements based on a defined criterion. An example of implementing a priority queue using a binary heap is provided, detailing the insertion and deletion processes. Understanding these concepts is essential for effectively utilizing PriorityQueue in programming.
#1
TenNen
97
0
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,
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.;
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
#6
Goalie_Ca
102
0
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
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:
Code:
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:
Code:
1
/ \
3 5
/ \ / \
6 7 8 9
/
2
Step 2
Heap: [1,3,5,2,7,8,9,6] =
Binary Tree:
Code:
1
/ \
3 5
/ \ / \
2 7 8 9
/
6
Step 3
Heap: [1,2,5,3,7,8,9,6] =
Binary Tree:
Code:
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:
Code:
6
/ \
2 5
/ \ / \
3 7 8 9
Heap Sort: O(n log n)
Code:
#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.
Last edited:
#8
TenNen
97
0
Goalie_Ca said:
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
