Requirements

In this sub-project, you will implement one class:

1. A stable binary (min) heap: Stable_binary_heap

A heap is said to be stable if two objects which are placed into the heap with the same value or priority, it follows that they will come out in the same order in which they were placed into the heap.

Suggestion: first get a binary heap working and only once it works perfectly for different integers should you try to add the stability.

Description

This class stores a fixed number of values in a binary minimum heap which is stable in the following sense: if two equal objects are placed into the heap, the object which was placed into the heap first is the first to be removed. If there are zero elements in the heap, the heap is said to be empty. The constructor is passed the capacity as an argument (defaulting to 10). The binary heap is to be implemented as is desribed in the course notes; however, some modifications will be necessary. The object at the top of the heap is always the smallest object of all objects in the heap (a min heap).

The process by which equal objects will be tracked is as follows: starting with 0, the first object entered into the heap is paired with the key 0, e.g., (x₁, 0). Following this, each successive object is given the next largest integer key. The key is never reset under any conditions. When determining order, use lexicographical ordering: (u, v) < (x, y) if u < x or u = x and v < y.

Basically, it is a binary heap where you keep track of a second array and if you make a swap in the first array (the standard heap), you make a similar swap in the second.

Because we are using integers and doubles to test your class, we will have access through the functions Type retrieve( int n ) const and int key( int n ) const.

Member Variables

Use whatever member variables you feel are necessary. Some member variables are suggested; however, you are welcome to modify them.

Member Functions

Constructors

Stable_binary_heap( int n = 10 )

This allocates enough memory for a heap capable of storing n objects.

Destructor

Any memory you allocated must be cleaned up. (O(1))

Copy Constructor

Create a copy of the object. (O(n))

Assignment Operator =

Assign the heap to be an exact copy, in all respects, of the argument. (O(n_rhs))

Accessors

This class has eight accessors:

int size() const;

Returns the number of items in the heap. (O(1))

int capacity() const;

Returns the number of items which can be stored in the heap. (O(1))

bool empty() const;

Returns true if the heap is empty, false otherwise. (O(1))

bool full() const;

Returns true if the heap is full, false otherwise. (O(1))

Type top() const;

Retrieves the object stored in the front of the heap. This function throws a underflow if the heap is empty. (O(1))

Type retrieve( int n ) const;

Returns the object stored in the nth location of the array implementation of the heap. The argument will always be between 1 and size(). This function is implemented for you. O(1)

int key( int n ) const;

Returns the key of the object stored in the nth location of the array implementation of the heap. The argument will always be between 1 and size(). This function is implemented for you. O(1)

int count( Type const &obj ) const;

Returns the number of objects in the heap which equal the argument obj. (O(n))

Mutators

This class has three mutators:

void push( Type const & );

This places the argument into the appropriate location in the heap as per the course notes and moves it up the heap as necessary. If the heap is full, throw an overflow exception. (average of O(1))

Type pop();

Dequeue the minimum element from the heap and return it. The heap must be modified as described in course notes. Be sure to keep track of the last element in the array. This function throws a underflow if the heap is empty. (O(ln(n)))

void clear();

Make the heap empty. It does not reset the key. (O(1))