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