Obtaining user logs! (Task 1)

Out of a lot of options that we had, we opted for OpenCart ( http://www.opencart.com/ ) for our front end e-commerce solution. So the first step was to download and configure open cart over a locally running LAMP server. The steps for setting up the OpenCart site on your Apache server can be found here : ” http://docs.opencart.com/display/opencart/Installation ” .

 

                      Image

 

Apache provides a mod_usertrack ( “http://httpd.apache.org/docs/2.0/mod/mod_usertrack.html ” ) module for logging the user activity by using cookies and generates a ‘clickstream’ log. An enhanced version of the same module can be found here by the name mod_cookietrack : ” https://github.com/piykumar/modified_mod_cookietrack ” . This module requires apache-dev to be installed and perl. After that you install it using the command ‘sudo ./build.pl’.

 

NOTE : If you have errors saying that apxs file is not found in /usr/sbin/apxs try to look for it in the folder /usr/bin/apxs and then copy it there!

 

Once that is done and the module has been successfully added to your Apache server, its time to provide the UUIDs for our logs. You see, the module has support for an external library to generate UUIDs. The function should be written in C and the prototype for the same being

void gen_uid(char *uid, char *timestamp, char *ip);

We have a basic function for it which generates UUIDs with the format “I….T…R…”, where the numbers after I are the IP address and those after T are the timestamp and three digits after R are random digits generated for uniqueness! 

Now that we have the function to generate the UUIDs, we add it to the module with the command, ‘ sudo ./build.pl –inc /where/uid/lives –lib uuid.c ‘.

The module has a many directives of which the CookieTracking directive has to be enabled for the tracking to begin. This can be done by adding the line ‘CookieTracking on’ in the server config file ie. either apache2.conf or httpd.conf. Some other useful directives are CookieExpires, CookieName, CookieNoteName etc. The details of all the directives are available in the documentation of mod_cookietrack.

                      Image

The CookieNoteName directive is used to refer to the UUID while generating custom logs. Here i have used the CookieNoteName uid for referring to the UUIDs. The name of the cookie here is ‘ocart’. Once done save the file and remember to restart the server with the command ‘ sudo service apache2 restart ‘.

Now you can go to your OpenCart site and check if the cookie is being created by the WebConsole( Ctrl+Shift+K ). Here is a what it should look like!

                     Image   

Notice that the cookie contains the name ‘ocart’ and the 64 bit UUID!

Finally we have to generate some custom logs. A really good place to learn more about generating server logs would be ” http://www.serverwatch.com/tutorials/article.php/1128861/Apache-Guide-Logging-Part-3–Custom-Logs.html “. First we have to define a log format and refer it by some name. And then define a directory for the custom logs to be stored.

                         Image

In line 211 i have defined a Log Format which displays just the UUID( ‘%{uid}n’ ) and the first line of the request( ‘%r’ ) and give it a referral name ‘client’ . Next in line 213 i have defined as to where these custom logs will be stored ie. /var/www/logs/c_logs. Once that is done remember to create the directory and touch the file in the appropriate directory. And ofcourse please do restart the server!

Go to your OpenCart site and start sending requests, you will then see the logs piling up in the c_logs file in /var/www/logs folder!

                    Image

So this is just the beginning! The first of the 5 tasks to continue! Cheers! 😀 \,,/

 

 

 

Advertisements

Basic Sorting Algorithms

In this post I will be talking about some basic and simple sorting algorithms. All of them have the same worst case running time of O(n2). The three sorting algorithms are Insertion Sort, Selection Sort, Bubble Sort.

INSERTION SORT:

Insertion sort is an in place sorting algorithm, which is efficient for small arrays. It is pretty stable and has a quite simple implementation. The procedure is very similar to taking cards from the deck into your hands while playing cards. When you pick a card from the deck you put it in the its right place in your hand. So at all times the cards in your hand are sorted.

The best case running time is when the array is already sorted, so a minimum number of comparisons are made. In this case the algorithm has linear running time. The worst case running time is when the array is reverse sorted, this is when maximum number of comparisons have to be made. It is even faster than quicksort when the size of the array to be sorted is small. The algorithm for insertion sort is,

INSERTION-SORT(A,n):
for j=2 to A.length
   key=a[j]
   i=j-1
   while A[i]>key and i>0
      A[i+1]=A[i]
      i=i-1
   A[i+1]=key

The C implementation for the same is,

#include<stdio.h>

int main()
{
	int i,j,n,a[10],key;
	
	printf("Enter size of array:");
	scanf("%d",&n);

	printf("\nEnter the elements:");
	for(i=0;i<n;i++) scanf("%d",&a[i]);

	for(j=1;j<n;j++)
	{
		key=a[j];
		i=j-1;
		while(i>=0 && a[i]>key)
		{
			a[i+1]=a[i];
			i=i-1;
		}
		a[i+1]=key;
	}

	printf("\nSorted array:");
	for(i=0;i<n;i++) printf("%d ",a[i]);

	return 0;
}

SELECTION SORT:

Insertion sort is also an in place algorithm but it inefficient compared to insertion sort. The array is divided into 2 sections, one sorted which is at the left and the other unsorted which comes after the previous sorted section. The technique is to fing the smallest element in the unsorted section and move it into the sorted section thus increasing the size of sorted section by 1 and decreasing the unsorted section by 1. The unsorted section is initially empty and filled later.

Analysis of the insertion sort shows that initially we scan the entire n elements to find smallest and replace it with the leftmost element. Next we scan the next n-1 elements to do the same, so as this goes on the array of elements we scan to find the smallest goes on decreasing ie. n+(n-1)+(n-2)+(n-3)+…+3+2+1=n(n-1)/2. Therefore it has the running time of O(n2).

The algorithm for it is,

SELECTION-SORT(A,n):
for i=1 to A.length-1
   small=A[i]
   pos=i
   for j=i to A.length
      if small>A[j]
         pos=j
         small=A[j]
   swap A[i] and A[pos]

The C implementation for the same is,

#include<stdio.h>

int main()
{
	int i,j,n,a[10],small,temp,pos;
	
	printf("Enter the size of array:");
	scanf("%d",&n);
	
	printf("\nEnter the array elements:");
	for(i=0;i<n;i++) scanf("%d",&a[i]);

	for(i=0;i<n;i++)
	{
		small=a[i];
		pos=i;
		for(j=i;j<n;j++)
		{
			if(a[j]<small)
			{
				small=a[j];
				pos=j;
			}
		}
		temp=a[i];
		a[i]=a[pos];
		a[pos]=temp;
	}

	printf("\nSorted array:");
	for(i=0;i<n;i++) printf("%d ",a[i]);

	return 0;
}

BUBBLESORT:

In bubblesort elements are repeatedly compared and exchamged and at the end of each outer loop the heaviest element lands at the bottom of the array(one of the reasons why it is called bubble sort). For an array of n elements the number of times that the outer loop runs is n-1. The inner loop just compare and exchanges the elements. One advantage of bubble sort is its ability to detect if the loop is already sorted.

The algorithm for bubble sort is,

BUBBLE-SORT(A,n):
for i=1 to A.length-1
   for j=A.length downto i+1
      if(A[j]<A[j-1]
         swap A[j] and A[j-1]

The C implementation for the same is,

#include<stdio.h>

int main()
{
	int i,j,n,a[10],key,temp;
	
	printf("Enter size of array:");
	scanf("%d",&n);

	printf("\nEnter the elements:");
	for(i=0;i<n;i++) scanf("%d",&a[i]);

	for(i=0;i<n;i++)
	{
		for(j=0;j<n-i;j++)
		{
			if(a[j+1]<a[j])
			{
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}

			
	printf("\nSorted array:");
	for(i=0;i<n;i++) printf("%d \n",a[i]);

	return 0;
}

The C code is reversely iterated on the array as opposed to the algorithm. Actually you can optimizing it to check if the array undergoes any swaps in a particular iteration, if not you can stop the sorting there as the array is sorted and the algorithm is just wasting time checking to see if it sorted.

Young’s Table

A Young’s table is a mxn matrix such that the entries of each row are in sorted order from left to right and the entries in each column are in sorted order from top to bottom. Some of the elements in the matrix can have the value infinity, which are actually non existing elements. The total number of elements is therefore less than or equal to mxn. And there can me be more than one representations of a Young’s table for a given set of elements.

The algorithms for all the Young’s Table operations are:
1.This operation sees to it that the Young’s Table condition is satisfied for a part of the matrix starting from index i,j and having size ixj.

YOUNGIFY(A,x,y):
small=A(x,y)

if y+1<=A.maxcolumn and A(x,y+1)<small
   small=A(x,y+1)
   p=x and q=y+1

if x+1<=A.maxrow and A(x+1,y)<small
   small=A(x+1,y)
   p=x+1 and q=y

if small!=A(x,y)
   swap values of A(x,y) and A(p,q)
   YOUNGIFY(A,p,q)

2. This is a operation to build the Young’s Table.

BUILD(A):
for i in range(A.maxrow,1)
   for(j in range(A.maxcol,1)
      YOUNGIFY(A,i,j)

3. This is the operation to extract the minimum element from the Young’s table.

EXTRACT-MIN(A):
min=A(1,1)
swap A(1,1) and A(A.maxrow,A.maxcol)
A.size=A.size-1
YOUNGIFY(A,1,1)

4. This is the operation to increase the value of an element at a particular index.

INCR(A,p,q):
large=A(p,q)

if p-1>=1 and p-1large
   large=A(p-1,q)
   x=p-1
   y=q

if q-1>=1 and q-1large
   large=A(p,q-1)
   x=p
   y=q-1

if large!=A(p,q)
   swap A(p,q) and A(x,y)
   INCR(A,x,y)

5. This is a operation to insert an element.

INSERT(A,key):
if A is full
   print 'Error'
   return
A.size+=1
A[A.maxrow][A.maxcolumn]=key
incr(A,A.maxrow,A.maxcolumn)

The running time of YOUNGIFY is O(m+n). And the running time of BUILD is n2 times O(m+n). Here m is A.maxrow and n is A.maxcolumn. All other operations take O(m+n) time. The C code for Young’s table is:

#include<stdio.h>
int m,n,num;

void youngify(int** a,int x,int y)
{
	int small,p,q,temp;
	small=a[x][y];
	p=x;
	q=y;

	if((y+1)<n && a[x][y+1]<small) 
	{
		small=a[x][y+1];
		p=x;
		q=y+1;
	}

	if((x+1)<m && a[x+1][y]<small)
	{
		small=a[x+1][y];
		p=x+1;
		q=y;
	}
		
	if(p!=x || q!=y)
	{	
		temp=a[x][y];
		a[x][y]=a[p][q];
		a[p][q]=temp;
		youngify(a,p,q);
	}

		
}

void build(int** a)
{
	int p,q,i,j;
		
	for(i=m-1;i>=0;i--)
	{
		for(j=n-1;j>=0;j--)
		{	youngify(a,i,j);
		}
	}	


}

int extract_min(int** a)
{
	int ret;

	ret=a[0][0];
	a[0][0]=a[m-1][n-1];
	num=num-1;
	youngify(a,0,0);
	return ret;
}

void display(int** a)
{
	int i,j;
	for(i=0;i<m;i++)
	{	for(j=0;j<n;j++)
		{
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}
}

void incr(int** a,int p,int q)
{
	int large=a[p][q],i,j,temp;
	
	if((p-1)>=0 && (p-1)<m && a[p-1][q]>large)
	{	large=a[p-1][q];
		i=p-1;
		j=q;
	}
	if((q-1)>=0 && (q-1)<n && a[p][q-1]>large)
	{
		large=a[p][q-1];
		i=p;
		j=q-1;
	}

	if(large!=a[p][q])
	{
		temp=a[p][q];
		a[p][q]=a[i][j];
		a[i][j]=temp;
		incr(a,i,j);
	}
}
		
	

void insert(int** a,int key)
{	
	if(num>=m*n)
	{
		printf("\nTable full!!!");
		return;
	}
	num=num+1;
	
	a[m-1][n-1]=key;
	incr(a,m-1,n-1);
}
	
	
	

int main()
{
	int i,j,k,arr[20];
	int** a;
	k=0;
	
	printf("Give the number of elements(max 20 and less than 999):");
	scanf("%d",&num);

	printf("\nSize of matrix:\nRows:");
	scanf("%d",&m);
	printf("\nColumns:");
	scanf("%d",&n);

	printf("\nGive the elements: ");
	for(i=0;i<num;i++)
	scanf("%d",&arr[i]);

	a=(int**)malloc(m*(sizeof(int*)));
	for(i=0;i<m;i++)
	a[i]=(int*)malloc(n*sizeof(int));
	
	for(i=0;i<m;i++)
	{	for(j=0;j<n;j++)
		{	if(k<num)
			{
				a[i][j]=arr[k];
				k+=1;
			}
			else
				a[i][j]=999;
		}
	}
	printf("\n");

	printf("\nThe initial Young's table is:\n");
	build(a);
	display(a);

	extract_min(a);
	printf("\nAfter extracting minimum element:\n");
	display(a);

	insert(a,1);
	printf("\nAfter inserting the element '1':\n");
	display(a);
	
	free(a);

	return 0;
}

Some of the changes in this code are that infinity is considered to be 999 and also the matrix starts from (0,0) unlike the algorithms where it starts from (1,1).

Merge Sort

Merge sort is a classic example of a divide and conquer algorithm. Here the array is divided in each step into half and sorted. The steps involved are
1. DIVIDE: Divide the array in half.
2. CONQUER: Sort the divided arrays recursively.
3. COMBINE: Combine them using a merge function.

Actually here the most important part is the merging, where we combine to small sorted arrays to form a larger sorted array. The algorithm for the merge operation is

MERGE(A,p,q,r):
n1=q-p+1
n2=r-q
Let L1 and R1 be the two sorted subarrays
for i=1 to n1
   L[i]=A[p+i-1]
for j=1 to n2
   R[i]=A[q+j]
L[n1+1]=infinity
R[n2+1]=infinity
for k=p to r
   if L[i]<R[j]
      A[k]=L[i]
      i=i+1
   else
      A[k]=R[j]
      j=j+1

Here we observe that MERGE algorithm runs in Θ(n) time. Next we implement the divide step using the following algorithm

MERGE-SORT:
if(p<r)
   q=(p+r)/2
   MERGE-SORT(A,p,q)
   MERGE-SORT(A,q,r)
   MERGE(A,p,q,r)

The base case for merge sort is when the array size drops down to one and the if condition results in a negation. The base case has a running time of Θ(1). Otherwise the array is divided in half on entering the conditional. Therefore the running time of merge sort is

         T(n)=  Θ(1)           if n=1
                2T(n/2)+Θ(n)   if n>1 

And this sums down to the running time of Θ(nlog n) when we analyse the recursion tree that we get for the function.
The C program to implement merge sort is as follows

#include<stdio.h>

void merge(int a[],int p,int q,int r)
{
	int i,j,b[10],k;
	i=p;
	j=r+1;
	k=p;
	
	while(i<=r && j<=q)
	{
		if(a[i]<a[j])
		b[k++]=a[i++];
		else
		b[k++]=a[j++];
	}

	while(i<=r)
	{
		b[k++]=a[i++];
	}

	while(j<=q)
	{
		b[k++]=a[j++];
	}

	for(i=p;i<=q;i++)
	a[i]=b[i];
}


void msort(int a[],int p,int q)
{	
	int r;
	if(p<q)
	{
		r=(p+q)/2;
		msort(a,p,r);
		msort(a,r+1,q);
		merge(a,p,q,r);
	}
}


int main()
{
	int n,a[10],i;
	
	printf("Enter size:");
	scanf("%d",&n);

	printf("\nEnter elements:");
	for(i=0;i<n;i++) scanf("%d",&a[i]);

	msort(a,0,n-1);

	printf("\nSorted elements:");
	for(i=0;i<n;i++) printf("%d ",a[i]);
	
	return 0;
}

Quick Sort

Quick sort has the best qualities of both merge sort and insertion sort. Like merge sort it is a divide and conquer algorithm and like insertion sort it sorts in place. The different parts of the algorithm are,

1.DIVIDE: Divide the array into 2 subarrays A[p…(q-1)] and A[(q+1)…r] such that all elements of A[p…(q-1)] are less that A[q] and all elements of A[(q+1)…r] are greater than A[q].

2.CONQUER: Sort arrays A[p…(q-1)] and A[(q+1)…r] recursively.

3.COMBINE: Because it is already sorted no work is needed for combining.

The different functions of quick sort are,

QUICKSORT(A,p,r):
if p<r
   q=PARTITION(A,p,r)
   QUICKSORT(A,p,q-1)
   QUICKSORT(A,q+1,r)
PARTITION(A,p,r):
pivot=A[r]
i=p-1
for j in (p to r-1)
   if A[j]<=pivot
      i=i+1
      swap A[i] and A[j]
swap A[i+1] and A[r]
return i+1

The PARTITION function divides array into 3 regions. They are,
1. p to i where elements are less than pivot
2. the pivot itself
3. i+2 to r where elements are greater than pivot

Running time of quick sort largely depends on how the PARTITION function divides the array ie. whether it is balanced or unbalanced.

Worst case of partitioning occurs when the an array of size n-1 and another of size 1 is returned. And if this goes on recursively

          T(n)=T(n-1) + T(1) + Θ(n)

This evaluates to Θ(n2) which is the running time of insertion sort. This occurs if it is already sorted or has same elements.

The best case occurs when the partition produces sub problems of size not more than n/2, in which case the running time is Θ(nlog n).

The C code for quick sort is

#include<stdio.h>

void swap(int *a,int *b)
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}	

int partition(int a[],int p,int r)
{
	int pivot,i,j;
	pivot=a[r];
	i=p-1;

	for(j=p;j<r;j++)
	{
		if(a[j]<pivot)
		{
			i=i+1;	
			swap(&a[i],&a[j]);
		}
	}
	
	swap(&a[i+1],&a[r]);
	return i+1;
}

void qsort(int a[],int p,int r)
{
	if(p<r)
	{
		int pivot;
		pivot=partition(a,p,r);
		qsort(a,p,pivot-1);
		qsort(a,pivot+1,r);
	}
}

int main()
{
	int n,a[20],i;
	
	printf("Enter size of array(max 20):");
	scanf("%d",&n);

	printf("\nEnter array elements:");
	for(i=0;i<n;i++) 
	{	scanf("%d",&a[i]);
	}

	qsort(a,0,n-1);

	printf("\nThe sorted array is: ");
	for(i=0;i<n;i++) 
	{	printf("%d ",a[i]);
	}
	
	return 0;
}

D-ary Heaps

D-ary heaps are same as ordinary binary heaps except that d-ary heaps have ‘d’ no. of children whereas binary heaps have 2 children. Here we consider the array indexing to start from 1. So the algorithm for all the heap operations are,

PARENT(i):
return ceil((i-1)/d)
CHILD(i):
t=i*(d-1)+(i-2)
return list(t+(0,...,d-1))
MAX-HEAPIFY(A,i,d):
max=A[i]
for j in CHILD(i)
   if A[j]>max
      max=A[j]
      pos=j
if max!=A[i]
   swap A[i] and A[pos]
   MAX-HEAPIFY(A,pos,d)

We notice that only these three basic functions have to be changed. Rest all are the same except that we use d everywhere which can be sent to the function as a parameter or d can be made a global variable which can be accessed everywhere. The C code for d-ary heap is

#include<stdio.h>

int d,heapsize;

void swap(int *a,int *b)
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

int parent(int i)
{
	return (i-1)/d;
}

int* child(i)
{
	int *a;
	a=malloc(sizeof(int)*d);
	int j;
	
	for(j=0;j<d;j++)
	a[j]=i*d+j+1;
	
	return a;
}

void heapify(int a[],int i)
{
	int *ch,largest,j;
	largest=i;
	ch=child(i);
	
	for(j=0;j<d;j++)
	{	if(a[largest]<a[ch[j]] && ch[j]<heapsize)
			largest=ch[j];
	}
		
	if(largest!=i)
	{	swap(&a[i],&a[largest]);
		heapify(a,largest);
	}
}

void build_heap(int a[],int n)
{
	int i;
	for(i=(n/d);i>=0;i--)
	heapify(a,i);
}
	
void display(int a[])
{
	int i,j,*ch;
	for(i=0;i<=(heapsize-1)/d;i++)
	{	ch=child(i);
		if(ch[0]<heapsize)
		{
		printf("%d : \n",a[i]);
		for(j=0;j<d;j++)
		if(ch[j]<heapsize)
		printf("-->%d\n",a[ch[j]]);
		}
	}
}


int heap_max(int a[])
{
	return a[0];
}

int extract_max(int a[])
{	
	if(heapsize<0)	
	{
		printf("Error:No Priority queue!!!");
		return 0;
	}	
	int max;
	max=a[0];
	a[0]=a[heapsize-1];
	heapsize=heapsize-1;
	heapify(a,0);
	return max;
}

void heap_key_incr(int a[],int i,int key)
{
	if(key<a[i-1])	
	{
		printf("\nError:Key less then current value!!");
		return;
	}
	i=i-1;
	a[i]=key;
	while(i>=0 && a[parent(i)]<a[i])
	{	swap(&a[parent(i)],&a[i]);
		i=parent(i);
	}
}

void heap_insert(int a[],int key)
{
	heapsize=heapsize+1;
	a[heapsize-1]=0;
	heap_key_incr(a,heapsize,key);
}

void heap_delete(int a[],int i)
{
	swap(&a[i],&a[heapsize-1]);
	heapsize=heapsize-1;
	heapify(a,0);
}

int main()
{	
	int a[20],i,n,ch,index,key;

	printf("Enter size of heap(max 20):");
	scanf("%d",&n);

        printf("Enter the no. of children:");
	scanf("%d",&d);

	heapsize=n;


	printf("\nEnter heap elements:");
	for(i=0;i<n;i++) 
	{	scanf("%d",&a[i]);
	}

	build_heap(a,n-1);
	display(a);

	while(1)
	{
	printf("\n\nMenu:\n1.Display\n2.Show maximum element\n3.Extract maximum element\n4.Increase key\n5.Insert element\n6.Delete element\n7.Exit");
	printf("\nChoice:");
	scanf("%d",&ch);
	
	switch(ch)
	{
		case 1:	display(a);
			break;
		case 2:	printf("\nMaximum element: %d",heap_max(a));
			break;
		case 3:	printf("\nExtracting maximum element from heap...");
			printf("\nMaximum element: %d",extract_max(a));
			printf("\nNew Heap:\n");
			display(a);
			break;
		case 4:	printf("\nIndex for changing key:");
			scanf("%d",&index);
			printf("\nNew key value:");
			scanf("%d",&key);
			printf("\nChanging key value...");
			heap_key_incr(a,index,key);
			printf("\nNew Heap:\n");
			display(a);
			break;
		case 5:	printf("\nNew element to be inserted:");
			scanf("%d",&key);
			heap_insert(a,key);
			printf("\nNew Heap:\n");
			display(a);
			break;
		case 6:	printf("\nIndex for deleting key:");
			scanf("%d",&index);
			heap_delete(a,index-1);
			printf("\nNew Heap:\n");
			display(a);
		case 7:	break;

	}
	if(ch==7) break;
	}

	return 0;
}

There is some amount of change in the algorithm used for PARENT,CHILD and HEAPIFY as in C the array indexing starts from 0 and not from 1 as assumed in the algorithms.

Priority Queues

A priority queue is a data structure for maintaining a set of objects or elements with its associated priority. One of the ways to implement priority queues is using heap data structure. There are 2 kinds of priority queues
1. Max Priority Queue
2. Min Priority Queue

Priority queues have the following functions
1. INSERT(s,x) : To insert a new element
2. MAXIMUM(s) or MINIMUM(s) : To find maximum priority element in a max or min priority queue
3. EXTRACT-MAX(S) or EXTRACT-MIN(s) : To extract and remove max or min element from the set
4. INCREASE-KEY(s,key) or DECREASE-KEY(s,key) : Increase priority in max queue and decrease priority in min queue
5. DELETE(A,i) : To delete element at index i

Max Priority Queues are usually used in job scheduling where jobs are given priorities and the job with highest priority is extracted from the set of all jobs and executed. Min Priority Queues are used for event simulation where events are to be simulated in a certain order and these events might inturn simulate many other things. The event is picked using EXTRACT-MIN and is simulated.

The pseudocode for the functions of Max Priority Queue are:

HEAP_MAXIMUM(A):
return A[1]
HEAP-EXTRACT-MAX(A):
if A.heapsize<1
   error 'Heap Underflow'
max=A[1]
A[1]=A[heapsize]
A.heapsize=A.heapsize-1
MAX-HEAPIFY(A,1)
return max

The HEAP-EXTRACT-MAX(A) function has running time O(lg n) as the MAX-HEAPIFY runs from 1 ie. the root so has height lg n.


HEAP-INCR-KEY(A,i,key):
if key<A[1]
   error 'New key smaller than current one!!!'
A[i]=key
while i>1 and A[PARENT(i)]<A[i]
   swap A[PARENT(i)] and A[i]
   i=PARENT(i)

Again the running time of HEAP-INCR-KEY(A,i,key) is O(lg n) as it climbs up the heap exchanging if the if condition is true.


MAX-HEAP-INSERT(A,key):
A.heapsize=A.heapsize+1
A[A.heapsize]=-(infinity)
HEAP-INCR-KEY(A,A.heapsize,key)

For obvious reasons the running time is O(lg n).


HEAP-DELETE(A,i):
swap A[i] and A[A.heapsize]
A.heapsize=A.heapsize-1
MAX-HEAPIFY(A,i)

Guess the running time for this one…

The C code for Max Priority Queue is

#include<stdio.h>

int heapsize=-1;

void swap(int *a,int *b)
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

int parent(int i)
{	
	if(i!=0)	
	{	if(i%2==0)	return (i-1)/2;
		else	return i/2;
	}
}

int left(int i)
{
	return 2*i+1;
}

int right(int i)
{
	return 2*i+2;
}

void max_heapify(int a[],int i)
{
	int l,r,largest;
	l=left(i);
	r=right(i);
	
	if(l<heapsize && a[l]>a[i])	largest=l;
	else	largest=i;

	if(r<heapsize && a[r]>a[largest])	largest=r;

	
	if(largest!=i)
	{
		swap(&a[i],&a[largest]);
		max_heapify(a,largest);
	}
}

void build_max_heap(int a[],int n)
{
	int i;	
	heapsize=n+1;
	for(i=n/2;i>=0;i--)	
	max_heapify(a,i);
}

void display(int a[])
{
	int i;

	for(i=0;i<=heapsize/2;i++)
	{
		if(left(i)<heapsize && right(i)<heapsize)		
		printf("%d Left--> %d\n  Right-->%d\n",a[i],a[left(i)],a[right(i)]);
		else if(left(i)<heapsize && right(i)>=heapsize)
		printf("%d Left--> %d\n",a[i],a[left(i)]);
	}

}

int heap_max(int a[])
{
	return a[0];
}

int extract_max(int a[])
{	
	if(heapsize<0)	
	{
		printf("Error:No Priority queue!!!");
		return 0;
	}	
	int max;
	max=a[0];
	a[0]=a[heapsize-1];
	heapsize=heapsize-1;
	max_heapify(a,0);
	return max;
}

void heap_key_incr(int a[],int i,int key)
{
	if(key<a[i-1])	
	{
		printf("\nError:Key less then current value!!");
		return;
	}
	i=i-1;
	a[i]=key;
	while(i>=0 && a[parent(i)]<a[i])
	{	swap(&a[parent(i)],&a[i]);
		i=parent(i);
	}
}

void heap_insert(int a[],int key)
{
	heapsize=heapsize+1;
	a[heapsize-1]=0;
	heap_key_incr(a,heapsize,key);
}

void heap_delete(int a[],int i)
{
	swap(&a[i],&a[heapsize-1]);
	heapsize=heapsize-1;
	max_heapify(a,0);
}

int main()
{
	int n,a[20],i,ch,key,index;
	
	printf("Enter size of heap(max 20):");
	scanf("%d",&n);

	printf("\nEnter heap elements:");
	for(i=0;i<n;i++) 
	{	scanf("%d",&a[i]);
	}

	printf("\nBuilding a max heap...\n\n");
	build_max_heap(a,n-1);

	display(a);

	printf("\nArray:");
	for(i=0;i<n;i++) printf("%d ",a[i]);

	while(1)
	{
	printf("\n\nMenu:\n1.Display\n2.Show maximum element\n3.Extract maximum element\n4.Increase key\n5.Insert element\n6.Delete element\n7.Exit");
	printf("\nChoice:");
	scanf("%d",&ch);
	
	switch(ch)
	{
		case 1:	display(a);
			break;
		case 2:	printf("\nMaximum element: %d",heap_max(a));
			break;
		case 3:	printf("\nExtracting maximum element from heap...");
			printf("\nMaximum element: %d",extract_max(a));
			printf("\nNew Heap:\n");
			display(a);
			break;
		case 4:	printf("\nIndex for changing key:");
			scanf("%d",&index);
			printf("\nNew key value:");
			scanf("%d",&key);
			printf("\nChanging key value...");
			heap_key_incr(a,index,key);
			printf("\nNew Heap:\n");
			display(a);
			break;
		case 5:	printf("\nNew element to be inserted:");
			scanf("%d",&key);
			heap_insert(a,key);
			printf("\nNew Heap:\n");
			display(a);
			break;
		case 6:	printf("\nIndex for deleting key:");
			scanf("%d",&index);
			heap_delete(a,index-1);
			printf("\nNew Heap:\n");
			display(a);
		case 7:	break;

	}
	if(ch==7) break;
	}
	return 0;
}

The Minimum Priority Queue implementation is very similar.