Im taking an algorithm class and my notes say that a heapcan

I\'m taking an algorithm class and my notes say that a heapcan be used to implement a priority queue. I\'m not sure how this works but Could Heap-Maximum(A), Heap-Extract-Max(A), and Max-Heap-Insert(A, key) be illustrated with an example? Also what are the algorithms?

Also what are the running times and why?

Thanks,

Solution

using heaps to implement prioity queues for inserting and deleting takes O(log n) time.Based on implementation priorty queues is of two types like max-priority queue,min-priority queue.

max-priority queue can be implemented in the following ways.....

Heap_Maximum(A) - it returns the maximum element in array A.

Heap_Extract_Max(A) - it removes and removes the maximum element in array A.

Max_Heap_Insert(A,key) - it inserts key into A.

Max_Heap_Increase_val(A,i,key) - it increases the key of element stored at index i in A to new value key.

Heap_Maximum(A) :-

int Heap_Maximum(A)

{

return A[1];   // as the maximum element is always the root element

}

complexity:O(1)

Heap_Extract_Max(A) :----

int Heap_Extract_Max(int A) {

if(length==0){

cout<\"cant remove as queue is empty\";

         return -1;

}

int max = A[1];

A[1] = A[length];

length=length-1;

max_heapify(A,1);//MAX_HEAPIFY FUNCTION IS GIVEN BELOW

return max;

}

complexity:O(log n)

Max_Heap_Increase_val :

int Max_Heap_Increase_val(int A, int i ,int key)

{

if( key < A[i])

{

cout<<\"new value is less than current value so it cant be inserted\";

return;

}

A[i]=key;

while(i > 1 and A[i/2] < A[i])

{

swap(A[i/2] , A[i]);

i=i/2;

}

}

complexity:O(logn)

Max_Heap_Insert(A,key)

int Max_Heap_Insert(int A,int key) {

length=length + 1;

A[length] = -1; // assuming all numbers greater than 0 are to be inserted in queue

Increase_Val(A ,length,key);

}

complexity:O(log n)

void max_heapify(int A[],int i ,int N)

{

int left = 2* i; //left child

int right = 2* i + 1;    //right child

if(left < = N and A[left] > A[i[)

{

largest = left;

}

if(right < = N and A[right] > A[i[)

{

largest = right ;

}

if(largest != i)

{

swap (A[i],A[largest]);

max_heapify(A,largest,N)

Extract Maximum

InsertValue:-