BinaryHeap

Priority queues are data structures which support fast insertion and extract-minimum operations. They are templated on both key and information fields, with the key field defining where the information sits in the heap.

  

Figure 2.13: BinaryHeap

  

Figure 2.14: Another BinaryHeap example

1. Creation

 

BinaryHeap<Key,Item> bh;

Create a binary heap of size BINHEAPSIZE (defined in general.h), with an array-based implementation. This is a fast priority queue if the number of elements is predetermined and unions are infrequent.

BinaryHeap<Key,Item> binary_heap_name( (int) n);

Create a binary heap of size n.

2. Operations

BinaryHeapNode<Key,Item>* insert (Key k, Item i)

Insert item i with key k into the heap, returning a pointer to the node containing it. $O(\log n)$

void remove (Item i)

This does nothing. It is defined with an empty body to provide a definition for the Container::remove(Item) method.

Item extractMin ()

Removes the node with minimum key from the heap and returns the information stored within. $O(\log n)$

Item get ()

Calls extractMin(). $O(\log n)$

BinaryHeapNode<Key,Item>* minimum ()

Return a pointer to the node containing the minimum item in the heap, but do not remove it. O(1)

Item min ()

Call minimum(), then extract the Item from the returned node. O(1)

int size ()

Return the number of items stored in the heap. An element count is always stored. O(1)

Bool emptyQ ()

Is the heap empty? O(1)

Bool fullQ ()

Is the heap full? O(1)

Bool memberQ (const Item&)

Is the item in the heap? O(n)

Bool sortedQ () const

Return FALSE. O(1).

void clear ()

Remove all the elements from the priority queue. O(n)

void decreaseKey (BinaryHeapNode<Key,Item>* node, Item k)

Decreases the value of the key in node to the new key value k. $O(\log n)$

void deleteKey (ContainerNode* node)

Remove the entry in noda from the heap. $O(\log n)$

ostream& display (ostream&)

Produce a human-readable display of the data structure. O(n)

friend ostream& operator<< (ostream& s, Heap<Item>& h)

Output h to output stream s. This is the inverse operation of >>.

ObjectType type ()

What type/implementation of priority queue is this?