Next: BinomialHeap Up: Priority Queue Dictionary Structures Previous: Priority Queue Dictionary Structures

### 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

Figure 2.14: Another BinaryHeap example
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.

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.

Item | get ()

Calls extractMin().

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.

void | deleteKey (ContainerNode* node)

Remove the entry in noda from the heap.

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?

Next: BinomialHeap Up: Priority Queue Dictionary Structures Previous: Priority Queue Dictionary Structures