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”

See also

http://analgorithmaday.blogspot.com/2011/01/heap-data-structure.html

http://analgorithmaday.blogspot.com/2011/02/fun-with-bitwiseor-and-not-xor-and-left.html

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[0]

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[0]; }
 
    bool remove(int& val)
    {
        if(idx <= 0)
            return false;
 
        val = arr[0];
        arr[0] = 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!!