A binomial queue that contains *n* items consists of
at most binomial trees.
Each of these binomial trees is heap ordered.
In particular, the smallest key in each binomial tree
is at the root of that tree.
So, we know that the smallest key in the queue
is found at the root of one of the binomial trees,
but we do not know which tree it is.

The private member function `FindMinTree` is used to determine
which of the binomial trees in the queue has the smallest root.
As shown in Program ,
the `FindMinTree` simply traverses the entire linked list
to find the tree with the smallest key at its root.
Since there are at most binomial trees,
the worst-case running time of `FindMinTree` is

**Program:** `BinomialQueue` Class `FindMinTree` and `FindMin` Member Function Definitions

Program also defines the public `FindMin` function
which returns the smallest key in the priority queue.
The `FindMin` function uses `FindMinTree` to locate the
tree with the smallest key at its root
and returns a reference to that key.
Clearly, the asymptotic running time of `FindMin` is the same
as that of `FindMinTree`.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.