C++ Program to Implement D-ary Heap
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
/*
* D-ary Heap Class
*/
class DaryHeap
{
private:
int d;
int currentSize;
int size;
int *array;
public:
/*
* Constructor
*/
DaryHeap(int capacity, int numKids)
{
currentSize = 0;
d = numKids;
size = capacity + 1;
array = new int[capacity + 1];
for (int i = 0 ; i < capacity + 1; i++)
array[i] = -1;
}
/*
* Constructor , filling up heap with a given array
*/
DaryHeap(int* array, int numKids)
{
int i = 0;
while (array[i] != -1)
i++;
currentSize = i;
this->array = array;
this->d = numKids;
buildHeap();
}
/*
* Function to check if heap is empty
*/
bool isEmpty()
{
return currentSize == 0;
}
/*
* Check if heap is full
*/
bool isFull()
{
return currentSize == size;
}
/*
* Clear heap
*/
void makeEmpty( )
{
currentSize = 0;
}
/*
* Function to get index parent of i
*/
int parent(int i)
{
return (i - 1) / d;
}
/*
* Function to get index of k th child of i
*/
int kthChild(int i, int k)
{
return d * i + k;
}
/*
* Function to inset element
*/
void insert(int x)
{
if (isFull())
{
cout<<"Array Out of Bounds"<<endl;
return;
}
int hole = currentSize;
currentSize++;
array[hole] = x;
percolateUp(hole);
}
/*
* Function to find least element
*/
int findMin()
{
if (isEmpty())
{
cout<<"Array Underflow"<<endl;
return 0;
}
return array[0];
}
/*
* Function to delete element at an index
*/
int Delete(int hole)
{
if (isEmpty())
{
cout<<"Array Underflow"<<endl;
return 0;
}
int keyItem = array[hole];
array[hole] = array[currentSize - 1];
currentSize--;
percolateDown( hole );
return keyItem;
}
/*
* Function to build heap
*/
void buildHeap()
{
for (int i = currentSize - 1 ; i >= 0; i--)
percolateDown(i);
}
/*
* Function percolateDown
*/
void percolateDown(int hole)
{
int child;
int tmp = array[hole];
for ( ; kthChild(hole, 1) < currentSize; hole = child)
{
child = smallestChild( hole );
if (array[child] < tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}
/*
* Function to get smallest child from all valid indices
*/
int smallestChild(int hole)
{
int bestChildYet = kthChild(hole, 1);
int k = 2;
int candidateChild = kthChild(hole, k);
while ((k <= d) && (candidateChild < currentSize))
{
if (array[candidateChild] < array[bestChildYet])
bestChildYet = candidateChild;
k++;
candidateChild = kthChild(hole, k);
}
return bestChildYet;
}
/*
* Function percolateUp
*/
void percolateUp(int hole)
{
int tmp = array[hole];
for (; hole > 0 && tmp < array[parent(hole)]; hole = parent(hole))
array[hole] = array[ parent(hole) ];
array[hole] = tmp;
}
/*
* Function to print heap
*/
void printHeap()
{
cout<<"\nHeap = ";
for (int i = 0; i < currentSize; i++)
cout<<array[i]<<" ";
cout<<endl;
}
};
/*
* Main
*/
int main()
{
cout<<"Dary Heap Test\n\n";
cout<<"Enter size and D of Dary Heap: ";
int size, num, choice, val;
cin>>size>>num;
DaryHeap th(size, num);
char ch;
do
{
cout<<"\nDary Heap Operations\n";
cout<<"1. Insert "<<endl;
cout<<"2. Delete"<<endl;
cout<<"3. Check full"<<endl;
cout<<"4. Check empty"<<endl;
cout<<"5. Clear"<<endl;
bool chk;
cout<<"Enter your Choice: ";
cin>>choice;
switch (choice)
{
case 1:
cout<<"Enter integer element to insert: ";
cin>>val;
th.insert(val);
break;
case 2:
cout<<"Enter delete position: ";
cin>>val;
th.Delete(val - 1);
break;
case 3:
if (th.isFull())
cout<<"The Heap is Full"<<endl;
else
cout<<"The Heap is not Full"<<endl;
break;
case 4 :
if (th.isEmpty())
cout<<"The Heap is Empty"<<endl;
else
cout<<"The Heap is not Empty"<<endl;
break;
case 5 :
th.makeEmpty();
cout<<"Heap Cleared\n";
break;
default :
cout<<"Wrong Entry \n ";
break;
}
th.printHeap();
cout<<"\nDo you want to continue (Type y or n) \n";
cin>>ch;
}
while (ch == 'Y'|| ch == 'y');
return 0;
}
Output:
$ g++ dary_heap.cpp
$ a.out
Dary Heap Test
Enter size and D of Dary Heap: 6 3
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 24
Heap = 24
Do you want to continue (Type y or n)
y
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 6
Heap = 6 24
Do you want to continue (Type y or n)
y
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 23
Heap = 6 24 23
Do you want to continue (Type y or n)
y
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 12
Heap = 6 24 23 12
Do you want to continue (Type y or n)
y
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 75
Heap = 6 24 23 12 75
Do you want to continue (Type y or n)
y
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 78
Heap = 6 24 23 12 75 78
Do you want to continue (Type y or n)
y
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 29
Heap = 6 24 23 12 75 78 29
Do you want to continue (Type y or n)
y
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 2
Enter delete position: 5
Heap = 6 24 23 12 29 78
Do you want to continue (Type y or n)
y
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 2
Enter delete position: 6
Heap = 6 24 23 12 29
Do you want to continue (Type y or n)
y
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 2
Enter delete position: 3
Heap = 6 24 29 12
Do you want to continue (Type y or n)
y
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 5
Heap Cleared
