C++ Program to Implement D-ary-Heap

Hi Hello, What I am going to do in this article I will see in detail about C++ Program to Implement D-ary-Heap. This article is a favorite of everyone and many people are suffering without knowing what the reason is. This article will be very useful for them.

C++ Program to Implement D-ary-Heap

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 Testnn";

        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 Operationsn";

            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 Clearedn";

                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;

    }

Read Also: C++ Program to Implement CountMinSketch

Final Words

By knowing clearly about C++ Program to Implement D-ary-Heap through this article. If you have any doubts please leave a comment via the comment box. Thank You.

Hi, I'm Ranjith a full-time Blogger, YouTuber, Affiliate Marketer, & founder of Coding Deekshi. Here, I post about programming to help developers.

Share on:

Leave a Comment