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

Figure 1. A complete quaternary tree with 59 nodes.

Here is the class description:

Quaternary Heap
class Quaternary_heap<Type>

Accessors

bool empty() const

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

int size() const

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

int capacity() const

The capacity function returns the current capacity of the array storing the quaternary 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 quaternary heap. (Θ(1))

---

In addition to a clear implemention of a quaternary heap, there are quick-and-dirty implementations of both binary and quaternary min heaps. These attempt to optimize speed at the cost of clarity:

Heap2.h and Hepa4.h

These are used to test the relative speeds of binary and quaternary heaps using the files test.2.cpp and test.4.cpp which perform one billion random pushes and pops.

The sample test run yeilded times of:

66.519u 0.002s 1:04.64 99.9% 0+0k 0+0io 0pf+0w
55.741u 0.024s 0:55.80 99.9% 0+0k 0+0io 0pf+0w

for test.2.cpp and test.4.cpp, respectively, each compiled with the -O2 optimization option. In this case, the quaternary min heap is 16.2 % faster than a binary min heap.