C++ Program to Implement D-ary Heap

This C++ Program demonstrates the implementation of D-ary Heap.

Here is source code of the C++ Program to demonstrate the implementation of D-ary Heap. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 *  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;
```
```
}
```

$ 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
 
Heap =
 
Do you want to continue (Type y or n)
n
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Binary Heap

» Next - C++ Program to Implement Fibonacci Heap

Related Posts:

Apply for Computer Science Internship
Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ
Check Computer Science Books
Practice Computer Science MCQs

Recommended Articles: