17. 堆与优先队列¶

17.1. 堆与优先队列¶

无论是在现实生活中还是在计算应用中，都有许多情形需要我们从一组人、任务或对象中挑选出下一个"最重要的"。例如，医院急诊室的医生往往选择先看"最危急的"病人，而不是最先到达的那位。在多任务操作系统中调度待执行的程序时，任意时刻都可能有好几个程序（通常称为作业）已就绪、可以运行。下一个被选中的作业就是优先级最高的那个。优先级由与作业相关联的一个特定值来表示（并且在作业仍留在等待队列中时可能发生变化）。

当一组对象按重要性或优先级来组织时，我们称之为优先队列。普通的队列数据结构无法高效地实现优先队列，因为查找优先级最高的元素需要 \(\Theta(n)\) 时间。线性表无论是否排序，插入或删除都需要 \(\Theta(n)\) 时间。也可以使用按优先级组织记录的 BST，在平均情况下，总共 \(n\) 次插入和 \(n\) 次删除操作需要 \(\Theta(n \log n)\) 时间。然而，BST 总是有可能变得不平衡，从而导致糟糕的性能。因此，我们希望找到一种能保证在这种特殊应用中具有良好性能的数据结构。

本节介绍堆 [1] 数据结构。堆由两条性质来定义。首先，它是一棵完全二叉树，因此堆几乎总是用完全二叉树的数组表示来实现。其次，堆中存储的值是偏序的。这意味着任意结点存储的值与其子结点的值之间存在某种关系。根据这种关系的定义方式，堆有两种变体。

最大堆的性质是：每个结点存储的值都 大于或等于 其任一子结点的值。由于根结点的值大于或等于其子结点，而子结点又大于或等于它们的子结点，因此根结点存储着树中所有值的最大值。

最小堆的性质是：每个结点存储的值都 小于或等于 其子结点的值。由于根结点的值小于或等于其子结点，而子结点又小于或等于它们的子结点，因此根结点存储着树中所有值的最小值。

注意，在最小堆或最大堆中，一个结点的值与其兄弟结点的值之间都不存在必然的关系。例如，根结点左子树中所有结点的值完全可能都大于右子树中每个结点的值。我们可以通过比较排序关系的强弱来对比 BST 和堆。 BST 在其结点上定义了一种全序：给定树中任意两个结点的位置， "左边"的那个（等价地说，就是中序遍历中较早出现的那个）其键值小于"右边"的那个。相比之下，堆实现的是一种偏序。给定两个结点的位置，只有当 其中一个是另一个的后代时，我们才能确定这两个结点键值的相对次序。

最小堆和最大堆各有各的用途。例如，堆排序（Heapsort）使用最大堆，而用于外部排序的替换选择（Replacement Selection）算法使用最小堆。本节其余部分的示例将使用最大堆。

务必不要把堆的逻辑表示与通过基于数组的完全二叉树实现的物理实现相混淆。两者并不是同义的，因为堆的逻辑视图实际上是一种树结构，而典型的物理实现使用数组。

下面是最大堆的一种实现。该类使用支持 Comparable 接口的记录来提供灵活性。

Java
Java (Generic)

class MaxHeap {
  private int[] heap;   // Pointer to the heap array
  private int maxSize;  // Maximum size of the heap
  private int n;        // Number of things now in heap

  // Constructor supporting preloading of heap contents
  MaxHeap(int[] h, int num, int max)
    { heap = h; n = num; maxSize = max; buildHeap(); }

  // Return current size of the heap
  public int heapSize() { return n; }

  // Return true if pos a leaf position, false otherwise
  public boolean isLeaf(int pos) 
  { return (n / 2 <= pos ) && (pos < n); }

  // Return position for left child of pos
  public int leftchild(int pos) {
    if (pos >= n / 2) return -1;
    return 2 * pos + 1;
  }

  // Return position for right child of pos
  public int rightchild(int pos) {
    if (pos >= (n - 1) / 2) return -1;
    return 2 * pos + 2;
  }

  // Return position for parent
  public int parent(int pos) 
  { return (pos - 1) / 2; }

  // Insert val into heap
  public void insert(int key) {
    assert n < maxSize : "Heap is full; cannot insert";
    heap[n] = key;
    n++;
    siftUp(n - 1);
  }

  // Heapify contents of Heap
  private void buildHeap() {
    for (int i = parent(n - 1); i >= 0; i--) {
      siftDown(i);
    }
  }

  // Moves an element down to its correct place
  private void siftDown(int pos) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    while (!isLeaf(pos)) {
      int child = leftchild(pos);
      if ((child + 1 < n) && (heap[child + 1] > heap[child])) {
        child = child + 1; // child is now index with the greater value
      }
      if (heap[child] <= heap[pos]) {
        return; // stop early
      }
      swap(pos, child);
      pos = child; // keep sifting down
    }
  }

  // Moves an element up to its correct place
  private void siftUp(int pos) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    while (pos > 0) {
      int parent = parent(pos);
      if (heap[parent] > heap[pos]) {
        return; // stop early
      }
      swap(pos, parent);
      pos = parent; // keep sifting up
    }
  }

  // Remove and return maximum value
  public int removeMax() {
    assert n > 0 : "Heap is empty; cannot remove";
    n--;
    if (n != 0) {
      swap(0, n);  // Swap maximum with last value
      siftDown(0); // Put new heap root val in correct place
    }
    return heap[n];
  }

  // Remove and return element at specified position
  public int remove(int pos) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    n--;
    swap(pos, n); // Swap with last value
    update(pos);  // Move other value to correct position
    return heap[n];
  }

  // Modify the value at the given position
  public void modify(int pos, int newVal) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    heap[pos] = newVal;
    update(pos);
  }

  // The value at pos has been changed, restore the heap property
  private void update(int pos) {
    siftUp(pos);   // priority goes up
    siftDown(pos); // unimportant goes down
  }

  // swaps the elements at two positions
  private void swap(int pos1, int pos2) {
    int temp = heap[pos1];
    heap[pos1] = heap[pos2];
    heap[pos2] = temp;
  }
}

class MaxHeap<T extends Comparable<T>> {
  private T[] heap; // Pointer to the heap array
  private int maxSize; // Maximum size of the heap
  private int n; // Number of things now in heap

  // Constructor supporting preloading of heap contents
  MaxHeap(T[] h, int inSize, int max) {
    heap = h;
    n = inSize;
    maxSize = max;
    buildHeap();
  }

  // Return current size of the heap
  public int heapSize() { return n; }

  // Return true if pos a leaf position, false otherwise
  public boolean isLeaf(int pos) 
  { return (n / 2 <= pos ) && (pos < n); }

  // Return position for left child of pos
  public int leftChild(int pos) 
    { return 2 * pos + 1; }

  // Return position for right child of pos
  public int rightChild(int pos) 
  { return 2 * pos + 2; }

  // Return position for parent
  public int parent(int pos) 
  { return (pos - 1) / 2; }

  // Insert val into heap
  public void insert(T key) {
    assert n < maxSize : "Heap is full; cannot insert";
    heap[n] = key;
    n++;
    siftUp(n - 1);
  }

  // Heapify contents of Heap
  private void buildHeap() {
    for (int i = parent(n - 1); i >= 0; i--) {
      siftDown(i);
    }
  }

  // Moves an element down to its correct place
  private void siftDown(int pos) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    while (!isLeaf(pos)) {
      int child = leftChild(pos);
      if ((child + 1 < n) && (heap[child+1].compareTo(heap[child]) > 0)) {
        child++; // child is now index of child with greater value
      }
      if (heap[child].compareTo(heap[pos]) <= 0) {
        return; // stop early
      }
      swap(pos, child);
      pos = child; // keep sifting down
    }
  }

  // Moves an element up to its correct place
  private void siftUp(int pos) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    while (pos > 0) {
      int parent = parent(pos);
      if (heap[parent].compareTo(heap[pos]) > 0) {
        return; // stop early
      }
      swap(pos, parent);
      pos = parent; // keep sifting up
    }
  }

  // Remove and return maximum value
  public T removeMax() {
    assert n > 0 : "Heap is empty; cannot remove";
    n--;
    if (n != 0) {
      swap(0, n);  // Swap maximum with last value
      siftDown(0); // Put new heap root val in correct place
    }
    return heap[n];
  }

  // Remove and return element at specified position
  public T remove(int pos) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    n--;
    if (n != 0) {
      swap(pos, n); // Swap with last value
      update(pos);  // Move other value to correct position
    }
    return heap[n];
  }

  // Modify the value at the given position
  public void modify(int pos, T newVal) {
    assert (0 <= pos && pos < n) : "Invalid heap position";
    heap[pos] = newVal;
    update(pos);
  }

  // The value at pos has been changed, restore the heap property
  private void update(int pos) {
    siftUp(pos);   // priority goes up
    siftDown(pos); // unimportant goes down
  }

  // swaps the elements at two positions
  private void swap(int pos1, int pos2) {
    T temp = heap[pos1];
    heap[pos1] = heap[pos2];
    heap[pos2] = temp;
  }
}

这个类定义对使用基于数组的实现这一事实作了两点让步。首先，堆结点用它们在堆中的逻辑位置来表示，而不是用指向结点的指针来表示。实践中，堆的逻辑位置与数组中编号相同的物理位置相对应。其次，构造函数接受一个指向所用数组的指针作为输入。这种方式为使用堆提供了最大的灵活性，因为客户端可以把所有数据值直接加载到数组中。这样做的好处体现在堆的构建阶段，下文将加以说明。构造函数还接受一个整数参数，表示堆的初始长度（基于最初加载到数组中的元素个数），以及第二个整数参数，表示堆所允许的最大长度（即数组的长度）。

方法 heapsize 返回堆的当前长度。 H.isLeaf(pos) 在位置 pos 是堆 H 中的叶结点时返回 TRUE，否则返回 FALSE。成员 leftchild 、 rightchild 和 parent 分别返回所传入位置的左子结点、右子结点和父结点的位置（实际上就是数组下标）。

构建堆的一种做法是一次插入一个元素。方法 insert 会把一个新元素 \(V\) 插入堆中。

Settings

Saving...

Server Error
Resubmit

你可能以为堆的插入过程类似于 BST 的插入函数，从根开始、沿着堆向下进行。然而这种做法多半行不通，因为堆必须保持完全二叉树的形状。等价地说，如果在调用 insert 之前堆占据数组的前 \(n\) 个位置，那么在调用之后它必须占据前 \(n+1\) 个位置。为此， insert 先把 \(V\) 放在数组的位置 \(n\) 上。当然， \(V\) 多半不在正确的位置上。要把 \(V\) 移到正确位置，需要将它与其父结点的值进行比较。如果 \(V\) 的值小于或等于其父结点的值，那么它就在正确的位置上，插入例程就此结束。如果 \(V\) 的值大于其父结点的值，就交换这两个元素的位置。此后，把 \(V\) 与其（当前的）父结点进行比较的过程继续进行，直到 \(V\) 到达正确的位置。

由于堆是完全二叉树，其高度保证是最小的。具体来说，包含 \(n\) 个结点的堆，其高度为 \(\Theta(\log n)\) 。直观上可以看出这一定成立，因为我们每增加一层，树中结点数就会略多于原来的两倍（第 \(i\) 层有 \(2^i\) 个结点，前 \(i\) 层之和为 \(2^{i+1}-1\) ）。从 1 开始，只需翻倍 \(\log n\) 次就能达到 \(n\) 。准确地说，含 \(n\) 个结点的堆的高度为 \(\lfloor \log n \rfloor\) 。

在最坏情况下，每次调用 insert 需要 \(\Theta(\log n)\) 时间，因为被插入的值最多只能从树的底部移动到树的顶部。因此，如果一次插入一个值，把 \(n\) 个值插入堆中，在最坏情况下需要 \(\Theta(n \log n)\) 时间。

17.2. 构建堆¶

如果在构建过程开始时全部 \(n\) 个值都已可用，那么我们构建堆可以比逐个把值插入堆中更快。考虑下面这个例子，它给出了把一组初始值放入数组后建堆的两种可能方式。

Settings

Saving...

Server Error
Resubmit

Figure 11.17.1: 构建最大堆的两组交换序列。 (a) 这个堆是通过九次交换构建的，次序为 (4-2), (4-1), (2-1), (5-2), (5-4), (6-3), (6-5), (7-5), (7-6)。 (b) 这个堆是通过四次交换构建的，次序为 (5-2), (7-3), (7-1), (6-1)。

从这个例子可以清楚地看出，对于任意给定的一组数值，堆都不是唯一的，而且我们看到，有些重排输入值的方式比其他方式需要更少的交换来构建堆。那么，我们如何挑选最佳的重排方式呢？

一个很好的算法源于归纳法。假设根结点的左、右子树都已经是堆， \(R\) 是根结点元素的名称。下图展示了这种情形：

在这种情况下有两种可能。

(1) \(R\) 的值大于或等于其两个子节点。在这种情况下，构建完成。 (2) \(R\) 的值小于其一个或两个子节点。

应当把 \(R\) 与值较大的那个子结点交换。结果将是一个堆，只是 \(R\) 仍可能小于它的（新的）一个或两个子结点。在这种情况下，我们只需继续"向下推" \(R\) 的过程，直到它到达某个层次，在那里它大于其子结点，或者它本身就是叶结点。这个过程由私有方法 siftdown 实现。

这种做法假设子树已经是堆，这提示我们可以按某种次序访问结点来得到完整的算法，该次序保证一个结点的子结点在该结点之前被访问。一个简单的做法就是从数组的高下标向低下标进行处理。实际上，构建过程不必访问叶结点（它们已经位于底部，永远不可能下移），所以建堆算法可以从数组的中间、即第一个内部结点开始。

下面是建堆过程的可视化。

Settings

Saving...

Server Error
Resubmit

方法 buildHeap 实现了该构建算法。

buildHeap 的代价是多少？显然，它是各次 siftdown 调用代价之和。每次 siftdown 操作的代价最多等于被筛选的结点到达树底所需的层数。在任何完全二叉树中，大约一半的结点是叶结点，根本无法向下移动。四分之一的结点位于叶结点的上一层，因此它们的元素最多下移一层。树中每向上一层，结点数就减半，而高度增加一。因此，元素能够移动的总距离的最大值为

\[\sum_{i=1}^{\log n} (i-1)\frac{n}{2^i} = \frac{n}{2}\sum_{i=1}^{\log n} \frac{i-1}{2^{i-1}}.\]

右边的求和已知有一个约为 2 的闭式解，因此该算法在最坏情况下需要 \(\Theta(n)\) 时间。这远比逐个元素建堆要好，后者在最坏情况下需要 \(\Theta(n \log n)\) 时间。它也比构建 BST 所需的 \(\Theta(n \log n)\) 平均情况时间和 \(\Theta(n^2)\) 最坏情况时间更快。

Settings

Saving...

Server Error
Resubmit

17.3. 从堆中删除元素或更新对象的优先级¶

Settings

Saving...

Server Error
Resubmit

因为堆有 \(\log n\) 层深，删除最大元素的代价在平均和最坏情况下都是 \(\Theta(\log n)\) 。

Settings

Saving...

Server Error
Resubmit

对于某些应用，对象的优先级可能会被修改。这种情况下的一种解决方案是删除该对象再重新插入。为此，应用需要知道该对象在堆中的位置。另一种做法是改变对象的优先级值，然后更新它在堆中的位置。注意，删除操作本身无论如何都必须这样做，因为当堆中最后一个元素与被删除的那个元素交换时，那个值对于它的新位置而言可能太小，也可能太大。因此，我们在 remove 和 modify 两个方法中使用一个名为 update 的工具方法来处理这个过程。

17.4. 优先队列¶

堆是本节开头所讨论的优先队列的一种自然实现。作业可以在需要时加入堆（用其优先级值作为排序键）。每当要执行一个新作业时，就可以调用方法 removemax 。

有些优先队列应用需要能够改变已存储在队列中的对象的优先级。这可能要求更新该对象在堆表示中的位置。遗憾的是，最大堆在查找任意值时效率不高；它只适合查找最大值。不过，如果我们已经知道某个对象在堆中的下标，那么更新它的优先级（包括改变其位置以维持堆性质）或删除它就很简单了。 remove 方法接受要从堆中删除的结点的位置作为输入。对于需要更新优先级的优先队列，典型的实现需要使用一种支持高效查找对象的辅助数据结构（例如 BST）。辅助数据结构中的记录会存储对象的堆下标，以便更新对象的优先级。优先队列有助于求解图论问题，例如单源最短路径和最小代价生成树。

关于优先队列与龙的故事，见 Computational Fairy Tales: Stacks, Queues, Priority Queues, and the Prince's Complaint Line 。

OpenDSA 完整目录

Chapter 11 Binary Trees

17. 堆与优先队列¶

17.1. 堆与优先队列¶

17.2. 构建堆¶

17.3. 从堆中删除元素或更新对象的优先级¶

17.4. 优先队列¶