Algorithms - Queue/priority Queue
Queue implementations:
- Example 8
Queue Struct with linked list data structure. - Example 8B
Queue Class with linked list data structure.
A priority queue is a data structure, and it supports the following two basic operations:
- insert
- pop an item with the largest key
To implement the priority queue, we can use either unordered or ordered sequence, implemented as linked list or as arrays:
- Ordered sequence
This allows for constant-time remove the maximum and find the maximum,
but we may have to go through the whole list to insert an item. - Unordered sequence
This allows constant-time insert
but we may have to go through the whole list to find a maximum and remove the maximum.
The following code uses ordered linked list:
#include <iostream>
using namespace std;
typedef struct PriorityQueue
{
int data;
int pri;
PriorityQueue *next;
} pQ;
class PQueue
{
public:
PQueue();
~PQueue();
void push(int, int);
int pop();
void display();
private:
pQ *head;
};
PQueue::PQueue()
{
head = NULL;
}
void PQueue::push(int d, int pri)
{
pQ *ptr = new pQ;
ptr->data = d;
ptr->pri = pri;
ptr->next = NULL;
if(head == NULL) {
head = ptr;
return;
}
pQ *cur = head;
pQ *prev = head;
while(cur) {
if(pri > cur->pri) {
if(cur == head) {
pQ *old = head;
head = ptr;
head->next = old;
return;
}
prev->next = ptr;
ptr->next = cur;
return;
}
if(cur->next == NULL) {
cur->next = ptr;
return;
}
prev = cur;
cur = cur->next;
}
}
int PQueue::pop()
{
if(head == NULL) return -1;
int val = head->data;
pQ *old = head;
if(head->next) {
head = head->next;
delete old;
}
return val;
}
void PQueue::display()
{
pQ * cur = head;
while(cur) {
cout << cur->data <<":" << cur->pri << endl;
cur = cur->next;
}
}
int main()
{
PQueue *myPQueue = new PQueue();
myPQueue->push(4, 400);
myPQueue->push(5, 500);
myPQueue->push(1, 100);
myPQueue->push(2, 200);
myPQueue->push(3, 300);
myPQueue->display();
cout << "pop " << myPQueue->pop() << endl;
cout << "pop " << myPQueue->pop() << endl;
cout << "pop " << myPQueue->pop() << endl;
cout << "pop " << myPQueue->pop() << endl;
cout << "pop " << myPQueue->pop() << endl;
return 0;
}
Output:
5:500 4:400 3:300 2:200 1:100 pop 5 pop 4 pop 3 pop 2 pop 1
The following code uses unordered array, and index 0 not used:
#include <iostream>
using namespace std;
void swap(int&, int&);
class PQueue
{
public:
PQueue(int sz) : N(0) { pq = new int[sz];}
~PQueue() { delete[] pq; }
void insert(int item) {pq[++N] = item;}
int remove();
bool isEmpty() { return N == 0; }
void display();
private:
int *pq;
int N;
};
int PQueue::remove()
{
int max = 0;
for(int i = 1 ; i <= N; i++)
if(pq[max] < pq[i]) max = i;
/* swap the max item with the last item */
swap(pq[max], pq[N]);
/* return the last item which is not the max,
then reduce the array size by 1 */
return pq[N--];
}
void PQueue::display()
{
for(int i = 1; i <= N; i++) cout << pq[i] << " " ;
cout << endl;
}
void swap(int &a;, int &b;)
{
int temp = b;
b = a;
a = temp;
}
int main()
{
// first item of array a is not used
int a[] = {0, 19, 17, 16, 12, 9, 15, 1, 2, 11, 7, 3, 10, 14};
int sz = sizeof(a)/sizeof(a[0]);
PQueue *q = new PQueue(sz-1);
for(int i = 1; i < sz; i++) {
q->insert(a[i]);
}
q->display();
for(int i = 1; i < sz; i++) {
cout << "remove max " << q->remove() << endl;
q->display();
}
return 0;
}
Output should look like this:
19 17 16 12 9 15 1 2 11 7 3 10 14 remove max 19 14 17 16 12 9 15 1 2 11 7 3 10 remove max 17 14 10 16 12 9 15 1 2 11 7 3 remove max 16 14 10 3 12 9 15 1 2 11 7 remove max 15 14 10 3 12 9 7 1 2 11 remove max 14 11 10 3 12 9 7 1 2 remove max 12 11 10 3 2 9 7 1 remove max 11 1 10 3 2 9 7 remove max 10 1 7 3 2 9 remove max 9 1 7 3 2 remove max 7 1 2 3 remove max 3 1 2 remove max 2 1 remove max 1
Here we used unordered sequence (array). If we use ordered array, we can remove the maximum and find the maximum in constant-time. But we may go through the whole list for insert while unordered array allows a constant-time insert but more work needed to find the maximum and remove the maximum.
In this example, we constructs a heap by inserting items one by one starting from an empty heap. Throughout the inserting process, we keep the array in heap order by moving sequentially through the array using siftUp(). The time complexity of the process is NlogN for the worst case, but on the average, it's linear time.
The code below is the extension of the previous example. To insert an element, we incremented N by 1, and add the new item at the end of the heap. Then, we used siftUp() to restore the max-heap condition. In the remove(), the heap size is decremented by 1, and we take the value to be returned from pq[1], which is actually pq[N] after the swap.
Note that index 0 is not used, and the valid array arrange is from pq[1] to pq[N].
#include <iostream>
using namespace std;
void swap(int&, int&);
class PQueue
{
public:
PQueue(int sz) : N(0) { pq = new int[sz];}
~PQueue() { delete[] pq; }
void insert(int);
int remove();
bool isEmpty() { return N == 0; }
void display();
void siftDown(int*, int, int);
void siftUp(int*, int);
private:
int *pq;
int N;
};
void PQueue::siftUp(int a[], int k)
{
while(k > 1 && a[k] > a[k/2]) {
swap(a[k], a[k/2]);
k = k/2;
}
}
void PQueue::siftDown(int a[], int k, int n)
{
while(2*k <= n )
{
int child = 2*k;
if(child < n && a[child] < a[child+1]) child++;
if(a[k] < a[child]) {
swap(a[k], a[child]);
k = child;
}
else
return;
}
}
void PQueue::insert(int item)
{
pq[++N] = item;
siftUp(pq, N); // N is the last index
}
// remove max element
int PQueue::remove()
{
swap(pq[N], pq[1]);
// N is the last index, pq[N] is the max about to be removed
siftDown(pq, 1, N-1); // move down
return pq[N--]; // Now, N is the max item index
}
void PQueue::display()
{
for(int i = 1; i <= N; i++) cout << pq[i] << " " ;
cout << endl;
}
void swap(int &a;, int &b;)
{
int temp = b;
b = a;
a = temp;
}
int main()
{
int a[] = {0, 19, 17, 16, 12, 9, 15, 1, 2, 11, 7, 3, 10, 14};
int sz = sizeof(a)/sizeof(a[0]);
PQueue *q = new PQueue(sz-1);
for(int i = 1; i < sz; i++) {
q->insert(a[i]);
}
q->display();
for(int i = 1; i < sz; i++) {
cout << "remove max " << q->remove() << endl;
q->display();
}
return 0;
}
When we insert a new element, we use siftUp() to restore max-heap condition by moving up the heap. Actually, we swap the node at k with its parent at k/2. We do this as long as a[k/2] < a[k] until we get to the top of the heap.
Output is:
19 17 16 12 9 15 1 2 11 7 3 10 14 remove max 19 17 14 16 12 9 15 1 2 11 7 3 10 remove max 17 16 14 15 12 9 10 1 2 11 7 3 remove max 16 15 14 10 12 9 3 1 2 11 7 remove max 15 14 12 10 11 9 3 1 2 7 remove max 14 12 11 10 7 9 3 1 2 remove max 12 11 9 10 7 2 3 1 remove max 11 10 9 3 7 2 1 remove max 10 9 7 3 1 2 remove max 9 7 2 3 1 remove max 7 3 2 1 remove max 3 2 1 remove max 2 1 remove max 1
As we see from the output, the array always keeps the max-heap condition.
Ph.D. / Golden Gate Ave, San Francisco / Seoul National Univ / Carnegie Mellon / UC Berkeley / DevOps / Deep Learning / Visualization
My YouTube channel