Code:
#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;
}
Output:
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
More C++ Programs:
