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. $O(\log n)$

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. $O(\log n)$

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. $O(\log n)$

Item get ()

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

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. $O(\log n)$

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

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

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

Merges the contents of H into the current heap. $O(\log n)$

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. $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?