Next: General Dictionary Structures Up: Priority Queue Dictionary Structures Previous: BinaryHeap

### BinomialHeap

1. Creation

BinomialHeap<Key,Item> | bnh;

Create a binomial heap, which may contain an arbitrary number of items, and supports fast unions.

2. Operations

BinomialHeapNode<Key,Item>* | insert (Key k, Item i)

Insert item i with key k into the heap, returning a pointer to the HeapNode containing it.

void | search (const Key&)

Searches the heap for the passed key. O(n)

void | searchItem (const Item&)

Searches the heap for the passed item. O(n)

void | remove (BinomialHeapNode<Key,Item>* n)

Removes n from the heap.

void | remove (Item i)

Removes n from the heap by first searching for i, then removing the node containing it. O(n)

Item | extractMin ()

Removes the node with minimum key from the heap and returns the information stored within.

Item | get ()

Calls extractMin().

BinomialHeapNode<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 ()

Return FALSE. O(1)

void | clear ()

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

void | changeKey (HeapNode* node, Key k)

Change the value of the key in node to the new key value k.

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

Decreases the value of the key in node to the new key value k.

void | merge (BinomialHeap<Key,Item>& H)

Merges the contents of H into the current heap.

void | scramble()

Randomly permute the contents of the data structure without losing the priority queue property. Useful for testing. O(n)

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: General Dictionary Structures Up: Priority Queue Dictionary Structures Previous: BinaryHeap