This is an implementation of Ian Munro and Hendra Suwanda's bi-parental heaps:
a heap data structure where each node has two children and one or two parents and where
each node must be both less than any children and greater than any parent.

Figure 1 shows a bi-parental heap with 17 objects.

Figure 1. A bi-parental heap.

The strength and weakness of a bi-parental heap is that the height of the
heap is approximately √2√*n* and the average depth of a node
is approximately 2/3*h* and therefore all operations are
**O**(√*n*) **including** arbitrary find and count functions
while maintaining a run time **Θ**(1) access to the top element.
In this spirit, this implementation, in addition, ensures that the unused
memory is nevery greater than **O**(√*n*).

A bi-parental heap may be stored as an array (like a binary heap) but
determining membership or finding the largest object are **O**(*n*)
operations. Using an AVL tree will allow all operations to run in
**Θ**(ln(*n*)) run time this is a node-based storage format
requiring Θ(*n*) additional memory.

Insertions (pushes) occur at the next empty location, shown in Figure 2,
and are percolated up.

Figure 2. Insertion into a bi-parental heap.

Searching may be performed in O(√n) run time as is shown
in Figure 3 which demonstrates the trace of a search for the value 44.

Figure 3. A search through a bi-parental heap for 44.

# Bi-parental Heap

`class Beap<Type>`

## Constructors

`Beap<Type>( int h = 3 )`

The constructor creates a bi-parental heap of initial capacity for a heap of
height *h*. By default, this is 3 storing 10 objects.

`Beap<Type>( Beap const &beap )`

The constructor creates a bi-parental heap which is an exact copy
of the argument.

## Destructor

`~Beap<Type>()`

The destructor deallocates the memory used by the array.

## Assignment

`Beap<Type> &Beap<Type>::operator=( Beap<Type> const &rhs )`

Assignment makes a deep copy of the right-hand side of the assignment.

## Accessors

`bool empty() const`

The `empty` function returns true if the heap is empty and
false otherwise. (**Θ**(1))

`int size() const`

The `size` function returns the number of objects stored within the bi-parental heap. (**Θ**(1))

`int capacity() const`

The `capacity` function returns the current capacity of the data structure storing the bi-parental heap. (**Θ**(1))

`int height() const`

The `height` function returns the height of the bi-parental heap. (**Θ**(1))

`Type top() const`

The `top` function returns the object at the top of (*i*.*e*., the next object to be popped from) of the bi-parental heap.
If the heap is empty, `Type()` is returned.
(**Θ**(1))

`Type back() const`

The `back` function returns the object at the back of (*i*.*e*., currently the last object to be popped from) of the bi-parental heap.
If the heap is empty, `Type()` is returned.
(**Θ**(√*n*))

`bool find( Type const &obj ) const`

Determines if the argument `obj` is in the bi-parental heap.
(**Θ**(√*n*))

`int count( Type const &obj ) const`

Returns the the number of occurances of the argument `obj` in the bi-parental heap.
(**Θ**(√*n*))

## Mutators

`void push( Type const &obj )`

Insert the argument `obj` into the bi-parental heap allowing duplication of objects. If the heap is full, add one more level
to the heap. This ensures that the unused memory is **O**(√*n*). (**Θ**(√*n*))

`void pop()`

Remove the top from the bi-parental heap. If this causes two rows of the heap to be empty, a new heap without the bottom
row is allocated.
This ensures that the unused memory is **O**(√*n*). (**Θ**(√*n*))

`void erase( Type const &obj )`

Remove all copies of the argument `obj` from the bi-parental heap. Not yet implemented.
(**Ω**(√*n*))

`void clear()`

The `clear` function empties the bi-parental heap. (**Θ**(*n*))