DataStructures
Class BinomialQueue

java.lang.Object
  |
  +--DataStructures.BinomialQueue

public class BinomialQueue

extends java.lang.Object

Implements a binomial queue. Note that all "matching" is based on the compareTo method.

Constructor Summary

BinomialQueue()
Construct the binomial queue.

Method Summary

Comparable	deleteMin() Remove the smallest item from the priority queue.
Comparable	findMin() Find the smallest item in the priority queue.
void	insert(Comparable x) Insert into the priority queue, maintaining heap order.
boolean	isEmpty() Test if the priority queue is logically empty.
boolean	isFull() Test if the priority queue is logically full.
static void	main(java.lang.String[] args)
void	makeEmpty() Make the priority queue logically empty.
void	merge(BinomialQueue rhs) Merge rhs into the priority queue.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BinomialQueue

public BinomialQueue()

Construct the binomial queue.

Method Detail

merge

public void merge(BinomialQueue rhs)
           throws Overflow

Merge rhs into the priority queue. rhs becomes empty. rhs must be different from this.

Parameters:

rhs - the other binomial queue.

Throws:

Overflow - if result exceeds capacity.

insert

public void insert(Comparable x)
            throws Overflow

Insert into the priority queue, maintaining heap order. This implementation is not optimized for O(1) performance.

Parameters:

x - the item to insert.

Throws:

Overflow - if capacity exceeded.

findMin

public Comparable findMin()

Find the smallest item in the priority queue.

Returns:

the smallest item, or null, if empty.

deleteMin

public Comparable deleteMin()

Remove the smallest item from the priority queue.

Returns:

the smallest item, or null, if empty.

isEmpty

public boolean isEmpty()

Test if the priority queue is logically empty.

Returns:

true if empty, false otherwise.

isFull

public boolean isFull()

Test if the priority queue is logically full.

Returns:

true if full, false otherwise.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.

main

public static void main(java.lang.String[] args)