12.2 ADT优先队列：ADT表的变体

ADT表按查找关键字组织数据，便于在给定了查找关键字的情况下检索某个项。这样，如果数据库需要按值来维护和查找，如本章前面描述的城市表，则应使用ADT表。此处分析与ADT表相关的另一种ADT，对一些应用程序而言，它更适用。

假设有病人到医院急诊室就诊。当病人进院时，工作人员将病人的记录输入数据库，供护士、医生和收费处检索。工作人员还必须跟踪急诊室病人，并确定每位病人接受治疗的时间。

ADT表适用于医院的普通数据库。急诊室工作人员应为病人使用什么ADT呢？使用ADT表，可按病人姓名的字母表顺序，或按ID号码的顺序诊治病人；使用队列，可按病人的到达顺序诊治病人。在这两种情况下，若Zither女士因急性阑尾炎到急诊室候诊，就必须等到Able先生将手上的一根小刺拔掉才能就诊。很明显，急诊室工作人员应为候诊患者指定某个紧急级别，或优先级。下一位医生应诊治优先级最高的病人。急诊室工作人员需要一个能根据优先级找出下一位候诊患者的ADT。

每日或每周的任务列表也是一个使用优先级的例子。设本周的工作安排如下：

● 将生日卡送给Mabel姑妈。

● 开始编写有关世界历史的研究论文。

● 读完《墙和镜子》一书的第12章。

● 制订周六晚上的计划。

在查阅列表时，一般会选择先处理优先级最高的任务。

优先级值可以表示病人的诊治优先级，或完成任务的优先级。应当为优先级值使用什么参量？这有很多可能，例如从1到10的简单数字。假设最大的优先级值指示最高的优先级。优先级值是表示数据项的记录的一部分。将各个项插入ADT，然后向ADT请求具有最高优先级的项。

这样的ADT称为优先队列(priority queue)。其正式定义是：优先队列是一个提供以下操作的ADT：

(1) 构建空优先队列。

(2) 确定优先队列是否为空。

(3) 将新项插入优先队列。

(4) 检索然后删除优先队列中具有最高优先级值的项。

图12-8是优先队列类的UML图。下面的伪码详细指定了ADT优先队列的操作：

PriorityQueue

items

createPQueue()

pqIsEmpty()

pqInsert()

pqDelete()

图12-8 优先队列类的UML图

// PQItemType is the type of the items

// stored in the priority queue.

+createPQueue()

// Creates an empty priority queue.

+pqIsEmpty():boolean｛query｝

// Determines whether a priority queue is empty.

+pqInsert(in newItem: PQItemType) throws PQueueException

// Inserts newItem into a priority queue. Throws

// PQueueException if priority queue is full.

+pqDelete(): PQItemType

// Retrieves and then deletes the item in a priority queue

// with the highest priority value.

这些操作类似于ADT表的一部分操作。显著区别在于pqDelete操作。tableRetrive和tableDelete表操作序列可以检索和删除查找关键字中包含给定值的项。pqDelete操作则可以检索和删除具有最高优先级值的项。注意，与tableRetrive和tableDelete不同，没有为pqDelete传递最高优先级的值。一般情况下，最高优先级的值是未知的，故很难用tableRetrieve和tableDelete完成该任务。另一方面，也不能使用pqDelete来检索和删除包含指定值的项。

由此看来，ADT优先队列和ADT表既有共同点，也有不同点。这可从它们的实现反映出来。开始时，先利用表的一些实现来实现优先队列。若优先队列中的项数很少，则可用有序的线性实现。基于数组的实现方案按优先级值的升序维护数据项，所以，具有最高优先级值的项在数组末端，如图12-9(a)所示。pqDelete只返回items[size-1]中的项，并使size减1。不过，在使用二叉查找确定插入位置后，pqInsert操作必须移动数组元素，为新项腾出空间。

如图12-9(b)所示，基于引用的线性实现按优先级值的降序排列各项，使具有最高优先级值的项处于链表开头。这样，pqDelete仅返回pqHead引用的项，然后将pqHead改为引用下一项。不过，pqInsert操作必须遍历链表，以确定正确的插入位置。这样，与表的线性实现一样，优先队列的线性实现面临着同样的困境。

图12-9 ADT优先队列的一些实现：(a)基于数组；(b)基于引用；(c)二叉查找树

考虑将二叉查找树作为优先队列的实现，如图12-9(c)所示。pqInsert操作与tableInsert操作相同，但在表操作中，并没有与pqDelete操作直接对应的操作。它必须在不知道最高优先级值的情况下查找包含该值的项。这个任务并不难，因为这一项一定是树中的最右节点。这样，只需跟踪rightChild引用，直至找到rightChild引用为null的节点为止(使用类似于二叉查找树的findLeftmost和deleteLeftmost方法，也可完成任务)。从树中删除这个节点也很容易，因为它最多只有一个子节点。

因此，对于表和优先队列而言，采用二叉查找树的实现都是一个不错的选择。但表和优先队列的用法不同。一些表应用程序主要涉及检索和遍历操作，故不影响二叉查找树的平衡。而优先队列不包含检索和遍历操作，它们的应用程序都涉及插入和删除，这将影响二叉查找树的形状。为此，应该使用第13章介绍的二叉查找树的均衡变体。若知道优先队列的最大项数，则堆的基于数组的实现是一个更好选择，详见下一节。采用堆的实现经常是优先队列最适合的选择，但基本不适用于表。

12.2.1 堆

堆是与二叉查找树类似的ADT，但又不同于二叉查找树，主要体现在两个方面。第一，二叉查找树可看作是有序的，而堆在更弱的意义上有序。不过，这种有序足以使优先队列的操作高效执行。第二，二叉查找树有多种不同的形状，而堆总是完全二叉树。

堆是完全二叉树，可以为空，或者：

(1) 根包含的查找关键字大于等于各个子节点的查找关键字。

(2) 根包含作为子树的堆。

在这个堆的定义中，根项包含的查找关键字最大。这样的堆也称为maxheap。相对而言，minheap将包含最小查找关键字的项放在根中。练习题16将进一步分析minheap。

图12-10是类Heap的UML图。下面是堆操作的伪码：

Heap

items

createHeap()

heapIsEmpty()

heapInsert()

heapDelete()

图12-10 类Heap的UML图

// HeapItemType is the type of the items stored in the

// priority queue.

+createHeap()

// Creates an empty heap.

+heapIsEmpty():Boolean {query}

// Determines whether a heap is empty.

+heapInsert(in newItem: HeapItemType) throws HeapException

// Inserts newItem into a heap. Throws HeapException

// if heap is full.

+heapDelete(): HeapItemType

// Retrieves and then deletes a heap's root item.

// This item has the largest search key.

堆是完全二叉树，因此，若知道堆的最大项数，则可以用二叉树的基于数组的实现，如第10章所述。例如，图12-11显示堆及其数组表示。堆节点中的查找关键字大于等于其子节点的查找关键字。另外，在堆中，子节点的查找关键字彼此无关；换言之，并不知道哪个子节点包含的查找关键字更大。

图12-11 堆及数组表示

1. 堆的基于数组的实现

用下面的数据字段表示堆：

● items：堆项数组

● size：表示堆中项数的整数

数组items对应于树的基于数组的表示。在下面的讨论中，为简化起见，设堆项是整数。

2. heapDelete

首先考虑heapDelete操作。堆中最大的查找关键字在什么位置？因为各个节点的查找关键字都大于等于任一子节点的查找关键字，所以最大的查找关键字一定在树根中。这样，heapDelete操作的第1步为：

// return the item in the root

rootItem=item[0];

这很简单，但也必须删除根。在删除根后，将留下两个分离的堆，如图12-12(a)所示。因此，需要将剩余的节点再转化为堆。在开始转换时，取出树中最后一个节点的项，并将其放在根中，如下所示：

// copy the item from the last node into the root

items[O] = items[size-1]

// remove the last node

--size

图12-12 (a)分离堆；(b)半堆

如图12-12(b)所示，该步骤的结果不一定是堆。不过，这是一棵完全二叉树，其左右子树都是堆。唯一的问题是，根项不在正确的位置。这样的结构称为半堆(semiheap)。需要一种方式，将半堆转换为堆。一种策略是使根项逐渐下移，直到进入处于正确位置的节点为止。换言之，遍历树的其余部分，在查找关键字大于等于其子节点的查找关键字的第一个节点处停止，将该项放在这个节点中。为此，首先比较半堆根的查找关键字与其子节点的查找关键字。如果根的查找关键字小于子节点的查找关键字的较大者，则交换根与较大子节点的项。所谓较大的子节点，即查找关键字大于另一子节点的查找关键字的子节点。

图12-13显示了heapDelete操作。这个例子只做了一次交换，值5就下移至正确位置；不过，一般情况都需要多次交换。实际上，一旦交换了根项和较大子节点C的项，C就成为半堆的根(注意，节点C并不移动，更改的是它的值)。该策略推出了下面的迭归算法。

图12-13 从堆中删除

+heapRebuild(inout items:ArrayType, in root:integer,

in size:integer)

// Converts a semiheap rooted at index root into a heap.

// Recursively trickle the item at index root down to

// its proper position by swapping it with its larger

// child, if the child is larger than the item.

// If the item is at a leaf, nothing needs to be done.

if (the root is not a leaf) {

// root must have a left child

child = 2 * root + 1 // left child index

if (the root has a right child) {

rightChild = child + 1 // right child index

if (items[rightChild].getKey() > items[child].getKey()) {

child = rightChild // larger child index

// end if

// if the item in the root has a smaller search key

// than the search key of the item in the larger

// child, swap items

if (items[root].getKey() < items[child].getKey()) {

Swap items[root] and items[child]

// transform semiheap rooted at child into a heap

heapRebuild(items, child, size)

｝ // end if

// else root is a leaf, so you are done

图12-14演示了heapRebuild的递归调用。

图12-14 heapRebuild的递归调用

heapDelete操作使用heapRebuild，如下所示。

// return the item in the root

rootItem = items[0]

// copy the item from the last node into the root

items[0] = items[size-l]

// remove the last node

--size

// transform the semiheap back into a heap

heapRebuild(items, O, size)

return rootItem

简要分析一下heapDelete的效率。树存储在数组中，为删除节点，需要交换数组元素。这些交换值得关注，但不意味着算法的效率低下。数组的内容是引用，不必复制对象的数据，故交换速度很快。最多交换多少次数组元素？在heapDelete将树中最后一个节点的项复制到根之后，heapRebuild在树中下移此项，直至适当位置。在最坏的情况下，项从根出发，沿单个路径下移，到达叶子。因此，heapRebuild必须交换的数组项数不大于树的高度。如第11章所述，包含n个节点的完全二叉树的高度为。每个交换需要3次引用更改。因此，heapDelete需要的引用更改次数为：

3*+1

所以，heapDelete为O(log n)，实际上，这非常高效。

3. heapInsert

heapInsert算法的策略与heapDelete正好相反。heapInsert在树底插入一个新项，然后上移到适当位置，如图12-15所示。上移节点很容易，因为item[i]节点的父节点(不是根)总存储在item[(i–1)/2]中。heapInsert操作的伪码如下。

图12-15 在堆中插入

// insert newItem into the bottom of the tree

items[size] = newItem

// trickle new item up to appropriate spot in the tree

place = size

parent = (place-1)/2

while ( (parent >= 0) and

(items[place] > items[parent]) ) {

Swap items[place] and items[parent]

place = parent

parent = (place-1)/2

} // end while

Increment size

heapInsert的效率与heapDelete相同。换言之，在最坏的情况下，heapInsert必须交换从叶子到根的路径上的所有数组元素。故交换次数不超过树高。完全二叉树的高度为，因此heapInsert也为O(log n)。

堆的实现若不需要按查找关键字在堆中查找元素的方法，一般就只使用一个数据类型形参。但为了正确安排各个元素，必须提供比较对象的方法。这个实现采用JCF中许多实现都使用的技术，即允许通过Comparable接口对元素进行自然排序，或者为构造函数提供一个Comparator对象。如果没有提供Comparator对象，就把元素的类型用作数据类型实参，来实现Comparable接口。注意数据类型形参没有扩展Comparable接口，否则，在提供了Comparator对象的情况下，元素就不需要实现Comparable接口了。

下面的类是ADT堆的基于数组的实现。

package Heaps;

import java.util.ArrayList;

import java.util.Comparator;

public class Heap<T> {

private ArrayList<T> items; // array of heap items

private Comparator<? super T> comparator;

public Heap() {

items = new ArrayList<T>();

} // end default constructor

public Heap(Comparator<? super T> comparator) {

items = new ArrayList<T>();

this.comparator = comparator;

} // end default constructor

// heap operations:

public boolean heapIsEmpty() {

// Determines whether a heap is empty.

// Precondition: None.

// Postcondition: Returns true if the heap is empty;

// otherwise returns false.

return items.size() == 0;

} // end heapIsEmpty

public void heapInsert(T newItem)

throws HeapException, ClassCastException {

// Inserts an item into a heap.

// Precondition: newItem is the item to be inserted.

// Postcondition: If the heap was not full, newItem is

// in its proper position; otherwise HeapException is

// thrown.

if (!items.add(newItem)) {

// adding element to ArrayList item for heap

Throws new HeapException(“HeapException: heapInsert failed”);

} else {

// trickle new item up to its proper position

int place = items.size()-1;

int parent = (place - 1)/2;

while ( (parent >= 0) &&

(compareItems(items.get(place), items.get(parent)))<0){

// swap items[place] and items[parent]

T temp = items.get(parent);

Items.set(parent, items.get(place));

items.set(place, temp);

place = parent;

parent = (place - 1)/2;

} // end while

} // end if

} // end heapInsert

public T heapDelete() {

// Retrieves and deletes the item in the root of a heap.

// This item has the largest search key in the heap.

// Precondition: None.

// Postcondition: If the heap is not empty, returns the

// item in the root of the heap and then deletes it.

// However, if the heap is empty, removal is impossible

// and the method returns null.

T rootItem = null;

int loc;

if (!heapIsEmpty()) {

rootItem = items.get(0);

loc = items.size()-1;

// if we remove the item first, it may make the ArrayList items

// empty, then set() won’t work

items.set(0, items.get(loc));

items. remove(loc);

heapRebuild(0);

} // end if

return rootItem;

} // end heapDelete

protected void heapRebuild(int root) {

// if the root is not a leaf and the root's search key

// is less than the larger of the search keys in the

// root's children

int child = 2 * root + 1; // index of root's left

// child, if any

if ( child < items.size() ) {

// root is not a leaf, so it has a left child at child

int rightChild = child + 1; // index of right child,

// if any

// if root has a right child, find larger child

if ( (rightChild < items.size()) &&

(compareItems(items.get(rightChild)- items.get(child))) <0) {

child = rightChild; // index of larger child

} // end if

// if the root's value is smaller than the

// value in the larger child, swap values

if (compareItems(items.get(root). items.get(child))>0){

T temp = items.get(root);

Items.set(root, items.get(child));

Items.set(child, temp);

// transform the new subtree into a heap

heapRebuild(child);

} // end if

// if root is a leaf, do nothing

} // end heapRebuild

Private int compareItems(T item1, T item2) {

If (comparator == null) {

return ((Comparable<T>)item1). compareTo (item2);

} else {

Return comparator.compare(item1, item2);

} // end if

} // end compareItems

} // end Heap

12.2.2 ADT优先队列的堆实现

一旦实现了ADT堆，ADT优先队列的实现便迎刃而解，因为优先队列的操作与堆的操作非常相似。优先队列项的优先级值对应于堆项的查找关键字。所以，优先队列的实现可重用Heap类。换言之，PriorityQueue将Heap的实例作为其数据字段。

package PriorityQueues;

import Heaps.Heap;

import Heaps.HeapException;

import java.util.Comparator;

// *****************************************************

// Assumes that Heap implementation is in package Heaps.

// PriorityQueue class implementation.

// ****************************************************

public class PriorityQueue<T> {

private Heap<T> h;

public PriorityQueue() {

h = new Heap<T> ();

} // end default constructor

public PriorityQueue(Comparator<? super T> comparator) {

h = new Heap<T> (comparator);

} // end default constructor

// priority-queue operations:

public boolean pqIsEmpty() {

return h.heapIsEmpty();

} // end pqIsEmpty

public void pqInsert(T newItem)

throws PriorityQueueException {

try {

h.heapInsert(newItem);

} // end try

catch (HeapException e) { throw new PriorityQueueException(

"PQueueException: Problem inserting to Priority queue ");

} // end catch

} // end pqInsert

public T pqDelete() {

return h.heapDelete();

} // end pqDelete

} // end PriorityQueue

与二叉查找树相比，优先队列的堆实现如何？若知道优先队列的最大项数，则堆实现的效果更好。

堆是完全二叉树，因此总是平衡树，这是一个重要优点。若二叉查找树是平衡的，则在平均情况下，对于n个项，二叉查找树和堆实现具有相同的阶，都是O(log n)。不过，二叉查找树的高度在插入和删除操作期间可能发生增长，在最坏的情况下，将大大超过log₂n，把实现的效率降低为O(n)。而堆实现避免了性能的下降。

第13章将介绍如何保持二叉查找树的平衡性，但是，为解决这个问题，其操作的复杂性远远超过堆操作。不过，千万不要认为堆可替代二叉查找树，成为表的实现。如前所述，堆不适合扮演这个角色。如果对这个问题认识不清，可试着在堆上执行表操作tableRetrieve，或按查找关键字的顺序遍历堆。

有限、各不相同的优先级值若优先级值的数量有限，而且各不相同，如从整数1到20，则很多项具有相同的优先级值。可以按出现的先后顺序排列具有相同优先级值的项。

队列堆为每个不同的优先级值安排一个队列，可用来处理上述情况。在队列尚未就位的情况下，为了将项插入优先队列，可在堆上为该项的优先级值建立一个队列，然后将项插入该队列。要从优先队列中删除一项，可在堆中与最高优先级对应的队列中删除队首项。若该删除操作使队列变空，则将该队列从堆中删除。

章末的编程问题7进一步分析处理各不相同的优先级值。

12.2.3 堆排序

顾名思义，堆排序算法使用堆来排序无序的anArray数组。首先，算法将数组转换为堆。为完成转换，一种方法是使用heapInsert方法，将项逐一插入堆。

还有一种方法由数组anArray的项构建堆，这种方法效率更高。设anArray的原始内容如图12-16(a)所示。将数组anArray的项指派给树的节点，从根开始，从左到右，逐渐下移，构建一个二叉树。结果如图12-16(b)所示。此后，反复调用heapRebuild，将该树转换为堆。heapRebuild将半堆转换为堆。半堆的子树都是堆，但其根还未就位。但是，树中有供heapRebuild处理的半堆吗？图12-16(b)的树不是半堆，但查看叶子，可找到半堆；换言之，每个叶子是一个半堆(实际上，每个叶子是一个堆，但为简单起见，忽略了这个事实)。首先从右到左在叶子上调用heapRebuild，接着沿树上移，在到达节点s时，其子树为堆。于是，heapRebuild将以s为根的半堆转换为堆。

图12-16 (a)anArray的原始内容；(b)anArray的相应二叉树

下面的算法将包含n个项的anArray数组转换为堆，这是堆排序算法的第一步。

for (index = n - 1 down to 0)

// Assertion: the tree rooted at index is a semiheap

heapRebuild(anArray, index, n)

// Assertion: the tree rooted at index is a heap

实际上，在前面的for语句中，可用n/2替换n–1。章末编程问题21要求解释原因。图12-17跟踪对图12-16(a)中的数组执行该算法的过程。

图12-17 将anArray数组转换为堆

将数组转换为堆之后，堆排序将数组分为两个区域：Heap(堆)和Sorted(有序)，如图12-18所示。Heap区域在anArray[0..last]，Sorted区域在anArray[last+1..n–1]。开始时，Heap区域包含anArray的所有内容，而Sorted区域为空，换言之，last= n–1。

图12-18 堆排序将数组分为两个区域

在算法的每一步，将项I从Heap区域移到Sorted区域。堆排序算法的不变式为：

● 在步骤k后，Sorted区域包含anArray的k个最大值，且有序，换言之，anArray[n–1]是最大值，anArray[n–2]是第二个最大值，以此类推。

● Heap区域中的项构成堆。

只要保持不变式，I必然是Heap区域中的最大值项，故必为堆的根。为完成移动，交换堆的根项与堆的最后一项，换言之，交换anArray[0]与anArray[last]，然后将last的值减1。结果，刚从根交换到anArray[last]的项成为Sorted区域的最小项，且在Sorted区域的第一个位置。在移动后，将Heap区域转换为堆，因为新根的位置可能不对。可用heapRebuild下移根的当前项，使Heap区域再一次成为一个堆。

下面的伪码总结这些步骤：

+heapSort(in anArray:ArrayType, in n:integer)

// Sorts anArray[O..n-1].

// build initial heap

for (index = n - 1 down to O) {

// Invariant: the tree rooted at index is a semiheap

heapRebuild(anArray, index, n)

// Assertion: the tree rooted at index is a heap

} // end for

// Assertion: anArray[O] is the largest item in heap

// anArray[O..n-1]

// initialize the regions