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.