A ternary heap is a heap stored with a complete ternary tree: each node has up to three children and the nodes are filled in a breadth-first traversal order. An example of a complete ternary tree is shown in Figure 1.

Figure 1. A complete ternary tree with 59 nodes.

Here is the class description:

Ternary Heap
class Ternary_heap<Type>

Accessors

bool empty() const

Returns true if the ternary heap is empty. (Θ(1))

int size() const

The size function returns the number of objects stored within the ternary heap. (Θ(1))

int capacity() const

The capacity function returns the current capacity of the array storing the ternary heap. The capacity is doubled when the heap is filled and halved when the heap is one quarter full. (Θ(1))

int count( K const &key ) const

The count function returns the number of instances of key. (O(n))

Type top() const

Returns a copy of the object on top of the heap. (Θ(1))

Mutators

void push( Type const &obj )

The push function inserts the object into the heap. (amortized Θ(1))

void pop() const

The pop function removes the top object from the heap. (Θ(ln(n)))

void clear() const

The clear function removes all objects from the ternary heap. (Θ(1))