Monday, 14 February 2011

Priority Queue using binary heap

“Advantage of using binary heap for priority queue is that, remove operations are faster!! so that it can be used in a real time schedulers”

Introduction

Before jumping into priority queues which we already saw a metaphor example. We will study how to represent an array as a tree. Only if we understand how to represent array as a tree, it would be easy to do study tree representation using linked lists in future!!

What are all the terminologies?

PARENT = floor(i/2)

LEFT = 2i

RIGHT = 2i + 1

The above calculation is based on the assumption that “i” can never be zero or one.. So you cannot find the PARENT of a root, which would be 0 then.

But in all our calculations, we start with index 0. Since we start with zero, 1 and 2 becomes the right and left index of the root!!. so in our case,

PARENT = floor(i-1/2) && LEFT = 2i + 1  && RIGHT = 2i+2

Since we have already studied bitwise, we will use bitwise operators to represent these..

PARENT = i-1 >> 1 && LEFT = (i << 1) + 1 && RIGHT = (i << 1) + 2

The bit shift operations sometimes reduce the CPU instructions but not for the case when index is zero. :) for ex: for LEFT(i), mul and add is required.

int A[] = {15,13,9,5,12,8,7,4,0,6,2,1};

15                -----> 0

13                 9      ------> 1 , 2 (2i+1, 2i+2)

12         8         7       4    -----> 3, 4   5,6

0       6      2     1                    -----> 7,8   9, 10

Concept

The various operations in a priority queue ADT.

HEAP-INSERT – it behaves similar to build max heap!! insert elements

HEAP-EXTRACT-MAX – remove the maximum element (the root) and max heapify!!

HEAP-MAXIMUM – return the top element of the binary heap – A

HEAP-INCREASE-KEY – Change the key in a particular index and again make it a max heap

The heap sort can be implemented using the procedures given by the algorithm.

Code

#define PARENT(i)  (i-1)>>1

const int PQSIZE = 15;

class PriorityQueue
{
int arr[PQSIZE];
int idx;

public:
PriorityQueue()
{
idx=0;
}

bool insert(int val)
{
if(idx > PQSIZE)
return false;

arr[idx] = INT_MIN;
change(idx, val);
idx++;
return true;

}

int maximum() const { return arr; }

bool remove(int& val)
{
if(idx <= 0)
return false;

val = arr;
arr = arr[--idx];
arr[idx] = INT_MIN;
max_heapify(arr, 0, idx);
return true;
}

bool change(int i, int val)
{
if(val < arr[i])
return false;

arr[i] = val;
// the below loop never runs if the input
// array is already in maxheap format!!
while(i>0 && arr[PARENT(i)] < arr[i]) {
int tmp=arr[PARENT(i)];
arr[PARENT(i)] = arr[i];
arr[i] = tmp;
i = PARENT(i);
}
return true;
}
};

void main()
{
PriorityQueue pq;
int A[] = {4,0,13,15,8,7,12,6,2,1,9,5};

for(int i=0; i<12; i++)
{
pq.insert(A[i]);
}
int maxval = pq.maximum();
int remval = 0;
for(int i=0; i<15; i++)
{
pq.remove(remval);
}
}

Important points

• remove, change, insert all operates over array with index 0
• every remove does max heapify to rectify the correctness of the array
• similar to max heapify, insert also does a correctness of the array!!