C++ Program to Implement Ternary Heap

This C++ Program demonstrates the implementation of Ternary Heap.

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

```
/*
```

 * C++ Program to Implement Ternary Heap

```
 */
```
```
#include <iostream>
```
```
#include <cstdio>
```
```
#include <cstring>
```
```
#include <algorithm>
```
```
#include <cmath>
```
```
#include <vector>
```
```
#include <cstdlib>
```
```
int const N = 16;
```
```
using namespace std;
```
```
/*
```
```
 * Ternary Heap Class Declaration
```
```
 */
```
```
class Ternary_Heap
```
```
{
```
```
    private:
```
```
        int heap_capacity;
```
```
        int initial_capacity;
```
```
        int *array;
```
```
        int heap_size;
```
```
        void double_capacity()
```
```
        {
```

            int *tmp_array = new int[2 * capacity()];

            for (int i = 0; i < size(); ++i)

```
            {
```

                tmp_array[i] = array[i];

```
            }
```
```
            delete [] array;
```
```
            array = tmp_array;
```
```
            heap_capacity *= 2;
```
```
        }
```
```
        void halve_capacity()
```
```
        {
```

            int *tmp_array = new int[capacity() / 2];

            for (int i = 0; i < size(); ++i)

```
            {
```

                tmp_array[i] = array[i];

```
            }
```
```
            delete [] array;
```
```
            array = tmp_array;
```
```
            heap_capacity /= 2;
```
```
        }
```
```
    public:
```
```
        Ternary_Heap(int);
```
```
        ~Ternary_Heap();
```
```
        Ternary_Heap(Ternary_Heap &);
```

        Ternary_Heap &operator=(Ternary_Heap &heap);

        friend ostream &operator <<(ostream &, Ternary_Heap &);

```
        /*
```
```
         * Check if Heap is Empty
```
```
         */
```
```
        bool empty()
```
```
        {
```
```
            return heap_size == 0;
```
```
        }
```
```
        /*
```
```
         * Return Size of the Heap
```
```
         */
```
```
        int size()
```
```
        {
```
```
            return heap_size;
```
```
        }
```
```
        /*
```
```
         * Return Capacity of the Heap
```
```
         */
```
```
        int capacity()
```
```
        {
```
```
            return heap_capacity;
```
```
        }
```
```
        /*
```
```
         * Count elements in the Heap
```
```
         */
```
```
        int count(int &obj)
```
```
        {
```
```
            int c = 0;
```

            for (int i = 0; i < size(); i++)

```
            {
```
```
             if (array[i] == obj)
```
```
                ++c;
```
```
            }
```
```
            return c;
```
```
        }
```
```
        /*
```

         * Returns Top element of the Heap

```
         */
```
```
        int top()
```
```
        {
```
```
            if (empty())
```
```
                return NULL;
```
```
            return array[0];
```
```
        }
```
```
        /*
```

         * Push the element into the Heap

```
         */
```
```
        void push(int &obj)
```
```
        {
```
```
            if (size() == capacity())
```
```
                double_capacity();
```
```
            int i = heap_size;
```
```
            ++heap_size;
```

            while (i != 0 && array[(i - 1) / 3] > obj)

```
            {
```

                array[i] = array[(i - 1) / 3];

```
                i = (i - 1) / 3;
```
```
            }
```
```
            array[i] = obj;
```
```
        }
```
```
        /*
```

         * Remove element from the Heap

```
         */
```
```
        void pop()
```
```
        {
```
```
            if (empty())
```
```
                return;
```
```
            --heap_size;
```
```
            int last = array[size()];
```
```
            int posn = 0;
```
```
            int posn30 = 0;
```
```
            int posn33 = 3;
```
```
            while (posn33 < size())
```
```
            {
```

                int posn31  = posn30 + 1;

                int posn32 = posn30 + 2;

```
                int min = last;
```
```
                int loc = posn;
```

                if (array[posn33] < min)

```
                {
```

                    min = array[posn33];

```
                    loc = posn33;
```
```
                }
```

                if (array[posn32] < min)

```
                {
```

                    min = array[posn32];

```
                    loc = posn32;
```
```
                }
```

                if (array[posn31] < min)

```
                {
```

                    min = array[posn31];

```
                    loc = posn31;
```
```
                }
```
```
                array[posn] = min;
```
```
                if (posn == loc)
```
```
                {
```

                    if (4 * size() == capacity())

```
                    {
```

                        if (capacity() > initial_capacity)

```
                        {
```

                            halve_capacity();

```
                        }
```
```
                    }
```
```
                    return;
```
```
                }
```
```
                posn = loc;
```
```
                posn30 = 3 * loc;
```
```
                posn33 = posn30 + 3;
```
```
            }
```
```
            int min = last;
```
```
            int loc = posn;
```
```
            int posn31 = posn30 + 1;
```
```
            int posn32 = posn30 + 2;
```
```
            switch (posn33 - size())
```
```
            {
```
```
            case 0:
```

                if (array[posn32] < min)

```
                {
```

                    min = array[posn32];

```
                    loc = posn32;
```
```
                }
```
```
            case 1:
```

                if (array[posn31] < min)

```
                {
```

                    min = array[posn31];

```
                    loc = posn31;
```
```
                }
```
```
            }
```
```
            array[posn] = min;
```
```
            if (posn != loc)
```
```
            {
```
```
                array[loc] = last;
```
```
            }
```
```
        }
```
```
        /*
```
```
         * Clear Heap
```
```
         */
```
```
        void clear()
```
```
        {
```
```
            heap_size = 0;
```

            if (heap_capacity != initial_capacity)

```
            {
```

                heap_capacity = initial_capacity;

```
                delete [] array;
```

                array = new int[heap_capacity];

```
            }
```
```
        }
```
```
};
```
```
Ternary_Heap::Ternary_Heap(int n)
```
```
{
```
```
    heap_capacity = max(1, n);
```
```
    initial_capacity = heap_capacity;
```
```
    array = new int [heap_capacity];
```
```
    heap_size = 0;
```
```
}
```
```
 
```
```
Ternary_Heap::~Ternary_Heap()
```
```
{
```
```
    delete [] array;
```
```
}
```
```
 
```

Ternary_Heap::Ternary_Heap(Ternary_Heap &heap)

```
{
```
```
    heap_capacity = heap.heap_capacity;
```

    initial_capacity = heap.initial_capacity;

```
    array = new int [heap_capacity];
```
```
    heap_size = heap.heap_size;
```
```
    for (int i = 0; i < heap_size; i++)
```
```
    {
```
```
        array[i] = heap.array[i];
```
```
    }
```
```
}
```
```
 
```

Ternary_Heap &Ternary_Heap::operator=(Ternary_Heap &heap)

```
{
```
```
    if (this == &heap)
```
```
        return *this;
```

    if (heap_capacity != heap.heap_capacity)

```
    {
```
```
        delete [] array;
```

        heap_capacity = heap.heap_capacity;

        array = new int [heap_capacity];

```
    }
```

    initial_capacity = heap.initial_capacity;

```
    heap_size = heap.heap_size;
```
```
    for (int i = 0; i < size(); i++)
```
```
    {
```
```
        array[i] = heap.array[i];
```
```
    }
```
```
    return *this;
```
```
}
```
```
 
```

ostream &operator << (ostream &out, Ternary_Heap &heap)

```
{
```

    out << "Size:             " << heap.size() << endl;

    out << "Capacity:         " << heap.capacity() << endl;

    out << "Initial capacity: " << heap.initial_capacity << endl;

```
    out << "The Heap is:   ";
```

    for (int i = 0; i < heap.size(); ++i)

```
    {
```
```
        out << heap.array[i] << "   ";
```
```
    }
```
```
    out << endl;
```
```
    return out;
```
```
}
```
```
 
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main()
```
```
{
```
```
    Ternary_Heap heap(8);
```
```
    for (int i = 0; i < N; ++i) 
```
```
    {
```
```
        int x = (5 + 7 * i) % N;
```
```
        heap.push(x);
```
```
        cout << heap << endl;
```
```
    }
```
```
 
```
```
    for (int i = 0; i < N; ++i)
```
```
    {
```

        cout << "Current top: " << heap.top() << endl;

```
        heap.pop();
```
```
        cout << heap << endl;
```
```
    }
```
```
    cout << heap << endl;
```
```
    return 0;
```
```
}
```

$ g++ ternary_heap.cpp
$ a.out
 
Size:             1
Capacity:         8
Initial capacity: 8
The Heap is:   5
 
Size:             2
Capacity:         8
Initial capacity: 8
The Heap is:   5   12
 
Size:             3
Capacity:         8
Initial capacity: 8
The Heap is:   3   12   5
 
Size:             4
Capacity:         8
Initial capacity: 8
The Heap is:   3   12   5   10
 
Size:             5
Capacity:         8
Initial capacity: 8
The Heap is:   1   3   5   10   12
 
Size:             6
Capacity:         8
Initial capacity: 8
The Heap is:   1   3   5   10   12   8
 
Size:             7
Capacity:         8
Initial capacity: 8
The Heap is:   1   3   5   10   12   8   15
 
Size:             8
Capacity:         8
Initial capacity: 8
The Heap is:   1   3   5   10   12   8   15   6
 
Size:             9
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   5   10   12   8   15   6   13
 
Size:             10
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   4   10   12   8   15   6   13   5
 
Size:             11
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   4   10   12   8   15   6   13   5   11
 
Size:             12
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   4   2   12   8   15   6   13   5   11   10
 
Size:             13
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   4   2   12   8   15   6   13   5   11   10   9
 
Size:             14
Capacity:         16
Initial capacity: 8
The Heap is:   0   1   4   2   3   8   15   6   13   5   11   10   9   12
 
Size:             15
Capacity:         16
Initial capacity: 8
The Heap is:   0   1   4   2   3   8   15   6   13   5   11   10   9   12   7
 
 
Size:             16
Capacity:         16
Initial capacity: 8
The Heap is:   0   1   4   2   3   8   15   6   13   5   11   10   9   12   7   14
 
Current top: 0
Size:             15
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   4   2   7   8   15   6   13   5   11   10   9   12   14
 
 
Current top: 1
Size:             14
Capacity:         16
Initial capacity: 8
The Heap is:   2   3   4   9   7   8   15   6   13   5   11   10   14   12
 
Current top: 2
Size:             13
Capacity:         16
Initial capacity: 8
The Heap is:   3   7   4   9   12   8   15   6   13   5   11   10   14
 
Current top: 3
Size:             12
Capacity:         16
Initial capacity: 8
The Heap is:   4   7   5   9   12   8   15   6   13   14   11   10
 
Current top: 4
Size:             11
Capacity:         16
Initial capacity: 8
The Heap is:   5   7   6   9   12   8   15   10   13   14   11
 
Current top: 5
Size:             10
Capacity:         16
Initial capacity: 8
The Heap is:   6   7   10   9   12   8   15   11   13   14
 
Current top: 6
Size:             9
Capacity:         16
Initial capacity: 8
The Heap is:   7   8   10   9   12   14   15   11   13
 
Current top: 7
Size:             8
Capacity:         16
Initial capacity: 8
The Heap is:   8   12   10   9   13   14   15   11
 
Current top: 8
Size:             7
Capacity:         16
Initial capacity: 8
The Heap is:   9   12   10   11   13   14   15
 
Current top: 9
Size:             6
Capacity:         16
Initial capacity: 8
The Heap is:   10   12   15   11   13   14
 
Current top: 10
Size:             5
Capacity:         16
Initial capacity: 8
The Heap is:   11   12   15   14   13
 
Current top: 11
Size:             4
Capacity:         16
Initial capacity: 8
The Heap is:   12   13   15   14
 
Current top: 12
Size:             3
Capacity:         16
Initial capacity: 8
The Heap is:   13   14   15
 
Current top: 13
Size:             2
Capacity:         16
Initial capacity: 8
The Heap is:   14   15
 
Current top: 14
Size:             1
Capacity:         16
Initial capacity: 8
The Heap is:   15
 
Current top: 15
Size:             0
Capacity:         16
Initial capacity: 8
The Heap is:
 
Size:             0
Capacity:         16
Initial capacity: 8
The Heap is:
 
------------------
(program exited with code: 1)
Press return to continue