This is a fast, full-featured implementation of the priority queue. It is implemented as a dynamic array using the template Array<T>. Each element of the heap has a priority P and a pointer to template List<T>. When an element E of priority P is inserted, if P is already in the heap, then E is only inserted in the list of elements with priority P. If, on the other hand, P is not in the heap, only then will a new element be added to the heap with priority P, and then E is inserted in its list. A remove works in the opposite direction. If a list becomes empty, its priority is removed from the heap. The size of the underlying array is adjusted dynamically.

Note: Since the priority P is obtained from the element being inserted (or removed), the element (of type T) being inserted must have the following conversion as one of its member functions.

Example <ospace/advanced/examples/Heap.cpp>


  #include <ospace/advanced/Heap.h>
#include <ospace/std/iostream>

// Define type of elements to put in heap. We will use the attribute value for
//  priority.

class Element_Type 
   {
   public:
      Element_Type(void);
      Element_Type(string, int);
      const char* Name(void) {return name.c_str();}
      operator int(void) const {return value;} // The priority operator
   private:
      string name;
      int value;
   };

Element_Type::Element_Type(void) : name() 
   {
   value = 0;
   }

Element_Type::Element_Type(string n, int v) : name(n) 
   {
   value = v;
   }


int 
main( ) 
   {
   // Create a heap.
   os_HeapList<Element_Type, int> items;

   // Make a few items to put into the heap

   Element_Type bread("Bread", 50);
   Element_Type butter("Butter", 45);
   Element_Type sugar("Sugar", 40);
   Element_Type tea("Tea", 30);

   // Put them in the heap in any order. Heap will arrange them by priority

   items.insert(butter);
   items.insert(tea);
   items.insert(bread);
   items.insert(sugar);

   // Now remove items from heap and print their names. The output will be
   //  according to priority. Lower value means higher priority.

   while (items.Size()) cout << items.Head().Name() << endl;

   return 0;
   }