miles_span.w

模拟器提供了一个简单易用的平台

      v=w;
    }
    @<Rebuild |F_heap| from |new_roots|@>;
  }
  return final_v;
}

@ The work we do in this step is paid for by the unit of potential
energy being freed as |v| leaves the old forest, except for the
work of increasing~|h|; we charge the latter to the $O(\log n)$ cost of
building |new_roots|.

@<Put the tree rooted at |v| into the |new_roots| forest@>=
o,r=v->rank_tag>>1;
while (1) {
  if (h<r) {
    do@+{
      h++;
      o,new_roots[h]=(h==r?v:NULL);
    }@+while (h<r);
    break;
  }
  if (o,new_roots[r]==NULL) {
    o,new_roots[r]=v;
    break;
  }
  u=new_roots[r];
  o,new_roots[r]=NULL;
  if (oo,u->dist<v->dist) {
    o,v->rank_tag=r<<1; /* |v| is not critical and needn't be tagged */
    t=u;@+u=v;@+v=t;
  }
  @<Make |u| a child of |v|@>;
  r++;
}
o,v->rank_tag=r<<1; /* every root in |new_roots| is untagged */

@ When we get to this step, |u| and |v| both have rank |r|, and
|u->dist>=v->dist|; |u| is untagged.

@<Make |u| a child of |v|@>=
if (r==0) {
  o,v->child=u;
  oo,u->lsib=u->rsib=u;
}@+else {
  o,t=v->child;
  oo,u->rsib=t->rsib;
  o,u->lsib=t;
  oo,u->rsib->lsib=t->rsib=u;
}
o,u->parent=v;

@ And now we can breathe easy, because the last step is trivial.

@<Rebuild |F_heap| from |new_roots|@>=
if (h<0) F_heap=NULL;
else {@+long d; /* smallest key value seen so far */
  o,u=v=new_roots[h];
   /* |u| and |v| will point to beginning and end of list, respectively */
  o,d=u->dist;
  F_heap=u;
  for (h--;h>=0;h--)
    if (o,new_roots[h]) {
      w=new_roots[h];
      o,w->lsib=v;
      o,v->rsib=w;
      if (o,w->dist<d) {
        F_heap=w;
        d=w->dist;
      }
      v=w;
    }
  o,v->rsib=u;
  o,u->lsib=v;
}

@ @<Execute |jar_pr(g)| with Fibonacci heaps...@>=
init_queue=init_F_heap;
enqueue=enq_F_heap;
requeue=req_F_heap;
del_min=del_F_heap;
if (sp_length!=jar_pr(g)) {
  printf(" ...oops, I've got a bug, please fix fix fix\n");
  return -5;
}

@*Binomial queues.
Jean Vuillemin's ``binomial queue'' structures [{\sl CACM\/ \bf21} (1978),
@^Vuillemin, Jean Etienne@>
309--314] provide yet another appealing way to maintain priority queues.
A binomial queue is a forest of trees with keys ordered as in Fibonacci
heaps, satisfying two conditions that are considerably stronger than
the Fibonacci heap property: Each node of rank~$k$ has children of
respective ranks $\{0,1,\ldots,k-1\}$; and each root of the forest
has a different rank. It follows that each node of rank~$k$ has exactly
$2^k$ descendants (including itself), and that a binomial queue of
$n$ elements has exactly as many trees as the number $n$ has 1's in
binary notation.

We could plug binomial queues into the Jarn{\'\i}k/Prim algorithm, but
they don't offer advantages over the heap methods already considered
because they don't support the requeueing operation as nicely.
Binomial queues do, however, permit efficient merging---the operation
of combining two priority queues into one---and they achieve this
without as much space overhead as Fibonacci heaps. In fact, we can
implement binomial queues with only two pointers per node, namely a
pointer to the largest child and another to the next sibling. This means we
have just enough space in the utility fields of GraphBase |Arc| records
to link the arcs that extend out of a spanning tree fragment. The
algorithm of Cheriton, Tarjan, and Karp, which we will consider
soon, maintains priority queues of arcs, not vertices; and it
requires the operation of merging, not requeueing. Therefore binomial
queues are well suited to it, and we will prepare ourselves for that
algorithm by implementing basic binomial queue procedures.

Incidentally, if you wonder why Vuillemin called his structure a
binomial queue, it's because the trees of $2^k$ elements have many
pleasant combinatorial properties, among which is the fact that the
number of elements on level~$l$ is the binomial coefficient~$k\choose
l$. The backtrack tree for subsets of a $k$-set has the same
structure. A picture of a binomial-queue tree with $k=5$, drawn by
@^Knuth, Nancy Jill Carter@>
Jill~C. Knuth, appears as the frontispiece of {\sl The Art of Computer
Programming}, facing page~1 of Volume~1.

@d qchild a.A /* pointer to the arc for largest child of an arc */
@d qsib b.A /* pointer to next larger sibling, or from largest to smallest */

@ A special header node is used at the head of a binomial queue, to represent
the queue itself. The |qsib| field of this node points to the smallest
root node in the forest. (``Smallest'' means smallest in rank, not in
key value.) The header also contains a |qcount| field, which
takes the place of |qchild|; the |qcount| is the total number of nodes,
so its binary representation characterizes the sizes of the trees
accessible from |qsib|.

For example, suppose a queue with header node |h| contains five elements
$\{a,b,c,d,e\}$ whose keys happen to be ordered alphabetically. The first
tree might be the single node~$c$; the other tree might be rooted at~$a$,
with children $e$ and~$b$. Then we have
$$\vbox{\halign{#\hfil&\qquad#\hfil\cr
|h->qcount=5|,&|h->qsib=c|;\cr
|c->qsib=a|;\cr
|a->qchild=b|;\cr
|b->qchild=d|,&|b->qsib=e|;\cr
|e->qsib=b|.\cr}}$$
The other fields |c->qchild|, |a->qsib|, |e->qchild|, |d->qsib|, and
|d->qchild| are undefined. We can save time by not loading or storing the
undefined fields, which make up about 3/8 of the structure.

An empty binomial queue would have |h->qcount=0| and |h->qsib| undefined.

Like Fibonacci heaps, binomial queues store potential energy: The
number of energy units present is simply the number of trees in the forest.

@d qcount a.I /* this field takes the place of |qchild| in header nodes */

@ Most of the operations we want to do with binomial queues rely on
the following basic subroutine, which merges a forest of |m| nodes
starting at |q| with a forest of |mm| nodes starting at |qq|, putting
a pointer to the resulting forest of |m+mm| nodes into |h->qsib|.
The amortized running time is $O(\log m)$, independent of |mm|.

The |len| field, not |dist|, is the key field for this queue, because our
nodes in this case are arcs instead of vertices.

@<Prio...@>=
qunite(m,q,mm,qq,h)
  register long m,mm; /* number of nodes in the forests */
  register Arc *q,*qq; /* binomial trees in the forests, linked by |qsib| */
  Arc *h; /* |h->qsib| will get the result */
{@+register Arc *p; /* tail of the list built so far */
  register long k=1; /* size of trees currently being processed */
  p=h;
  while (m) {
    if ((m&k)==0) {
      if (mm&k) { /* |qq| goes into the merged list */
        o,p->qsib=qq;@+p=qq;@+mm-=k;
        if (mm) o,qq=qq->qsib;
      }
    }@+else if ((mm&k)==0) { /* |q| goes into the merged list */
      o,p->qsib=q;@+p=q;@+m-=k;
      if (m) o,q=q->qsib;
    }@+else @<Combine |q| and |qq| into a ``carry'' tree, and continue
             merging until the carry no longer propagates@>;
    k<<=1;
  }
  if (mm) o,p->qsib=qq;
}
    
@ As we have seen in Fibonacci heaps, two heap-ordered trees can be combined
by simply attaching one as a new child of the other. This operation preserves
binomial trees. (In fact, if we use Fibonacci heaps without ever doing
a requeue operation, the forests that appear after every |del_min|
are binomial queues.) The number of trees decreases by~1, so we have a
unit of potential energy to pay for this computation.

@<Combine |q| and |qq| into a ``carry'' tree, and continue
             merging until the carry no longer propagates@>=
{@+register Arc *c; /* the ``carry,'' a tree of size |2k| */
  register long key; /* |c->len| */
  register Arc *r,*rr; /* remainders of the input lists */
  m-=k;@+if (m) o,r=q->qsib;
  mm-=k;@+if (mm) o,rr=qq->qsib;
  @<Set |c| to the combination of |q| and |qq|@>;
  k<<=1;@+q=r;@+qq=rr;
  while ((m|mm)&k) {
    if ((m&k)==0) @<Merge |qq| into |c| and advance |qq|@>@;
    else {
      @<Merge |q| into |c| and advance |q|@>;
      if (mm&k) {
        o,p->qsib=qq;@+p=qq;@+mm-=k;
        if (mm) o,qq=qq->qsib;
      }
    }
    k<<=1;
  }
  o,p->qsib=c;@+p=c;
}

@ @<Set |c| to the combination of |q| and |qq|@>=
if (oo,q->len<qq->len) {
  c=q,key=q->len;
  q=qq;
}@+else c=qq,key=qq->len;
if (k==1) o,c->qchild=q;
else {
  o,qq=c->qchild;
  o,c->qchild=q;
  if (k==2) o,q->qsib=qq;
  else oo,q->qsib=qq->qsib;
  o,qq->qsib=q;
}

@ At this point, |k>1|.

@<Merge |q| into |c| and advance |q|@>=
{
  m-=k;@+if (m) o,r=q->qsib;
  if (o,q->len<key) {
    rr=c;@+c=q;@+key=q->len;@+q=rr;
  }
  o,rr=c->qchild;
  o,c->qchild=q;
  if (k==2) o,q->qsib=rr;
  else oo,q->qsib=rr->qsib;
  o,rr->qsib=q;
  q=r;
}

@ @<Merge |qq| into |c| and advance |qq|@>=
{
  mm-=k;@+if (mm) o,rr=qq->qsib;
  if (o,qq->len<key) {
    r=c;@+c=qq;@+key=qq->len;@+qq=r;
  }
  o,r=c->qchild;
  o,c->qchild=qq;
  if (k==2) o,qq->qsib=r;
  else oo,qq->qsib=r->qsib;
  o,r->qsib=qq;
  qq=rr;
}

@ OK, now the hard work is done and we can reap the benefits of the
basic |qunite| routine. One easy application enqueues a new arc
in $O(1)$ amortized time.

@<Prio...@>=
qenque(h,a)
  Arc *h; /* header of a binomial queue */
  Arc *a; /* new element for that queue */
{@+long m;
  o,m=h->qcount;
  o,h->qcount=m+1;
  if (m==0) o,h->qsib=a;
  else o,qunite(1L,a,m,h->qsib,h);
}

@ Here, similarly, is a routine that merges one binomial queue into
another. The amortized running time is proportional to the logarithm
of the number of nodes in the smaller queue.

@<Prio...@>=
qmerge(h,hh)
  Arc *h; /* header of binomial queue that will receive the result */
  Arc *hh; /* header of binomial queue that will be absorbed */
{@+long m,mm;
  o,mm=hh->qcount;
  if (mm) {
    o,m=h->qcount;
    o,h->qcount=m+mm;
    if (m>=mm) oo,qunite(mm,hh->qsib,m,h->qsib,h);
    else if (m==0) oo,h->qsib=hh->qsib;
    else oo,qunite(m,h->qsib,mm,hh->qsib,h);
  }
} 

@ The other important operation is, of course, deletion of a node
with the smallest key. The amortized running time is proportional to
the logarithm of the queue size.

@<Prio...@>=
Arc *qdel_min(h)
  Arc *h; /* header of binomial queue */
{@+register Arc *p,*pp; /* current node and its predecessor */
  register Arc *q,*qq; /* current minimum node and its predecessor */
  register long key; /* |q->len|, the smallest key known so far */
  long m; /* number of nodes in the queue */
  long k; /* number of nodes in tree |q| */
  register long mm; /* number of nodes not yet considered */
  o,m=h->qcount;
  if (m==0) return NULL;
  o,h->qcount=m-1;
  @<Find and remove a tree whose root |q| has the smallest key@>;
  if (k>2) {
    if (k+k<=m) oo,qunite(k-1,q->qchild->qsib,m-k,h->qsib,h);
    else oo,qunite(m-k,h->qsib,k-1,q->qchild->qsib,h);
  }@+else if (k==2) o,qunite(1L,q->qchild,m-k,h->qsib,h);
  return q;
}

@ If the tree with smallest key is the largest in the forest,
we don't have to change any links to remove it,
because our binomial queue algorithms never look at the last |qsib| pointer.

We use a well-known binary number trick: |m&(m-1)| is the same as
|m|, except that the least significant 1~bit is deleted.