A priority queue implemented using (dynamic) array. Heap is a fast priority queue. The priority is also a template parameter. In Heap<T, P> the T is the type of entities to store in heap, and P is the priority. Items with equal priority are kept in a list which can also be used as stack or queue by itself. Internal methods like percolate and sift have been written with care for efficiency.

The class instantiating the template parameter T must a method as follows : "operator P (void) const;". P is the second template type. Usually this will return an int for priority. Then, the type for T will have a method : "operator int(void) const {return pr;}" where pr is the priority.

Declaration


  
#include<ospace/advanced/Heap.h>

template
  <
  class entity
  class priority
  >
class os_HeapList

Interface

Constructor

os_HeapList(int m=32, int n=32)

This the default constructor. The values for m and n are for the underlying dynamic array.

Destructor

~os_HeapList()

Destroys all entries in the heap.

os_HeapList<T, P>& operator=(const os_HeapList<T, P>&)

The assignment operator.

make_empty

os_HeapList<T, P>& make_empty(void)

Removes and destroys the contents. The heap is in state of initial construction.

Size

unsigned int Size(void)

Returns the number of items in the heap.

insert

os_HeapList<T, P>& insert(const T& item)

Add item to head of list for its priority.

remove

os_HeapList<T, P>& remove(const T& item)

Removes the one occurrence of item from the heap.

remove_all

os_HeapList<T, P>& remove_all(const T& item)

Removes tall occurrences of item from the heap.

exists

int exists(const T& item)

Returns 1 (true) if item is in the heap. Otherwise returns 0 (false).

top

const T& top(void)

Returns a const reference to the top of heap, i.e. the top of list at top of heap.

head

T& head(void)

Returns a reference to the head of list at top of heap.

tail

T& entity(const T& item)

Returns a reference to the tail of list at top of heap.

append

os_HeapList<T, P>& append(const T& item)

Add item to tail of list for its priority.

Heap

Library

Declaration

Interface