Lately I have been studying Jon Bentley's book "Programming Pearl" and in the book it talks about priority queue with heap data structure. So I grabbed another book "Algorithms in C by Robert Sedgewick" and read more about it as it sounds pretty useful for many different applications.
According to these two books, a priority queue is a data structure to insert data and retrieve the item with either largest key or smallest key depending on your heap setup. We can implement priority queue using many different data structures but heap seems to be very good candidate. I borrowed two fundamental heap functions: siftdown() and siftup(). siftdown() sifts the first element down the data structure until it has either no child or it is larger than its children node and siftup() does the opposite.
So decided to implement it based on these two books and even though I referred the books, it was still somewhat tricky to get it right.
Tricky part was that I have to take care of a node with one child during siftdown(). At first I tried compare the node with both child in my while() loop but that did not work well. So referred the Algorithms in C for help and learned this edge case.
Followings are the code based on the two books I mentioned above. It needs more work if I need to use it for real but this should at least help me to get going.
typedef int node;
static node *pq;
static int N;
#define swap(a, b) \
do { node tmp = *a; *a = *b; *b = tmp; } while (0)
class prioQ
{
private:
node *pq;
int count;
int max_num;
public:
prioQ(int imax)
{
max_num = imax;
pq = new node[max_num+1];
count = 0;
}
~prioQ()
{
delete pq;
}
int empty()
{
return (count == 0);
}
int insert(node v)
{
if (count >= max_num) {
std::cout << "Queue is full." << std::endl;
return -1;
}
pq[++count] = v;
siftup(pq, count);
return 0;
}
node delmax()
{
if (empty()) {
std::cout << "No more item in the queue." << std::endl;
return -1;
}
swap(&pq[1], &pq[count]);
siftdown(pq, 1, count-1);
return pq[count--];
}
// helper functions from max heap
void siftup(node a[], int k)
{
while ((k > 1) && (a[k] > a[k/2])) {
swap(&a[k/2], &a[k]);
k = k / 2;
}
}
void siftdown(node a[], int k, int end)
{
int i;
while (k*2 <= end) {
i = k * 2;
// k*2 < N is to test one child node case
if ((k*2 < end) && (a[i] < a[i+1])) i++;
if (a[k] > a[i]) break;
swap(&a[k], &a[i]);
k = i;
}
}
};
