c11p622.txt

Data Abstraction & Problem Solving with C++源码

// ********************************************************
// Header file HeapException.h for the ADT heap.
// ********************************************************
#include <stdexcept>
#include <string>
using namespace std;

class HeapException: public logic_error
{
public:
   HeapException(const string & message = "")
                        : logic_error(message.c_str())
   { }
};  // end HeapException

// *********************************************************
// Header file Heap.h for the ADT heap.
// *********************************************************
const int MAX_HEAP = maximum-size-of-heap;
#include "HeapException.h"  
#include "KeyedItem.h"  // definition of KeyedItem

typedef KeyedItem HeapItemType;

class Heap
{
public:
   Heap();  // default constructor
   // copy constructor and destructor are
   // supplied by the compiler

// Heap operations:
   virtual bool heapIsEmpty() const;
   // Determines whether a heap is empty.
   // Precondition: None.
   // Postcondition: Returns true if the heap is empty;
   // otherwise returns false.

   virtual void heapInsert(const HeapItemType& newItem)
      throw(HeapException);
   // Inserts an item into a heap.
   // Precondition: newItem is the item to be inserted.
   // Postcondition: If the heap was not full, newItem is
   // in its proper position; otherwise HeapException is
   // thrown.

   virtual void heapDelete(HeapItemType& rootItem)
      throw(HeapException);
   // Retrieves and deletes the item in the root of a heap.
   // This item has the largest search key in the heap.
   // Precondition: None.
   // Postcondition: If the heap was not empty, rootItem 
   // is the retrieved item, the item is deleted from the
   // heap. However, if the heap is empty, removal is
   // impossible and the function throws HeapException.

protected:
   void heapRebuild(int root);
   // Converts the semiheap rooted at index root 
   // into a heap.

private:
   HeapItemType items[MAX_HEAP];  // array of heap items
   int          size;             // number of heap items
};  // end class
// End of header file.