## 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!!