Question

19.1 二项树与二项堆

19.1-1
x 不是根，则 degree[sibling[x]] < degree[x]
x 是根，则 degree[sibling[x]] > degree[x]
19.1-2
degree[p[x]] > degree[x]

19.2 对二项堆的操作

19.2-1

木有伪代码，直接看代码

//将 H1 和 H2 的根表合并成一个按度数的单调递增次序排列的链表
//不带头结点的单调链表的合并，返回合并后的头，不需要解释
node *Binomial_Heap::Binomial_Heap_Merge(Binomial_Heap *H1, Binomial_Heap *H2)
{
  node *l1 = H1->head, *l2 = H2->head, *ret = nil, *c = ret, *temp;
  while(l1 != nil && l2 != nil)
  {
    if(l1->degree <= l2->degree)
      temp = l1;
    else
      temp = l2;
    if(ret == nil)
    {
      ret = temp;
      c = ret;
    }
    else
    {
      c->sibling = temp;
      c = temp;
    }
    if(l1 == temp)l1 = l1->sibling;
    else l2 = l2->sibling;
  }
  if(l1 != nil)
  {
    if(ret == nil)
      ret = l1;
    else
      c->sibling = l1;
  }
  else
  {
    if(ret == nil)
      ret = l2;
    else
      c->sibling = l2;
  }
  delete H2;
  return ret;
}

19.2-2

19.2-3

19.2-5

如果可以将关键字的值置为正无穷，BINOMIAL-HEAP-MINIMUM 将无法区分二项堆为空和最小关键字为无穷大这两种情况，只需在返回加以区分即可

BINOMIAL-HEAP-MINIMUM(H)
1  y <- NIL
2  x <- head[H]
3  min <- 0x7fffffff
4  while x != NIL
5    do if key[x] < min
6        then min <- key[x]
7             y <- x
8        x <- sibling[x]
9  if min = 0x7fffffff and head[H] != NIL
10     then return head[H]
11   return y

19.2-6

不需要表示-0x7fffffff，只要比最小值小就可以了

BINOMIAL-HEAP-DELETE(H)
1  y <- BINOMIAL-HEAP-MINIMUM(H)
2  BINOMIAL-HEAP-DECREASE-KEY(H, x, key[y]-1)
3  BINOMIAL-HEAP-EXTRACT-MIN(H)

19.2-7

将一个二项堆 H 与一个二进制数 x 对应，对应方式 x=func(H) 为：

若 H 中有一棵二项树的根的度数为 k，则将 x 的第 k 为置 1。

（1）令一个二项堆 H1 有 x1=func(H1)，在 H1 上插入一个结点后变为 H2，有 x2=func(H2)，则 x2=x1+1

（2）令两个二项堆 H1、H2，H1、H2 合并后为二项堆 H3，，有 x1=func(H1)、x2=func(H2)、x3=func(H3)，则 x1+x2=x3

19.2-8

待解决