数据结构-C语言描述(第三版)第6章树.ppt

2. 堆的顺序存储表示 现在来定义堆的结构类型。由于我们从下标1开始存储堆中元素，所以在确定MaxSize的大小时应比实际使用值大1。 typedef struct minheap{ int Size, MaxHeap; T Elements[MaxSize]; }MinHeap; 堆中元素顺序存储在一维数组中，数组元素具有可比较大小的类型。 3. 向下调整和建堆运算 在实现建堆运算之前，我们先讨论堆的向下调整运算AdjustDown。AdjustDown运算的定义如下： void AdjustDown (T heap[], int r, int n) 　　设(heap[r+1], …, heap[n]) 这n－r个位置上的元素已满足heap[i]≤heap[2i] 且heap[i]≤heap[2i+1] (i=r+1, r+2, …, ?n/2?)的条件，则加入heap[r]后，使(heap[r], heap[r+1], …, heap[n]) 这n－r+1个位置上的元素满足堆的条件。 实现运算AdjustDown的方法是：向下调整heap[r]，设temp＝heap[r]，如果temp大于其左、右孩子中的较小者(即heap[2r] 和heap[2r+1]中的较小的元素)，则将temp与该较小元素交换，调整后继续将temp与它的左、右孩子中较小者比较；如果temp比较小的孩子的值大，再作交换，直到不再需要调整，或到达堆的底部为止。图6－22是AdjustDown运算的例子。图中，heap[3], heap[4], …，heap[9]已满足堆的条件，即heap[i]不大于heap[2i]和heap[2i+1]中的较小者，i=3，4。现调整heap[2]，调整过程见图6－22。 图6－22 向下调整算法举例 (a) 调整前r=2；(b) 92与18比较；(c) 92与50比较；(d) 保存92 建堆运算CreateHeap完成将一个以任意次序排列的元素序列，通过向下调整运算建成最小堆的功能。由于所有的叶子结点没有孩子，它们自然无须调整。调整从位置为(n/2(的元素开始，每次被调整的元素下标减1，重复调用AdjustDown函数，直到下标为1的元素调整后，建堆运算结束。向下调整和建堆运算的C语言程序见程序6－14。建堆运算的例子见表6－1。为了便于理解，读者也可使用如图6－22所示的完全二叉树形式来表示表6－1所描述的建堆过程。 表6－1 建 堆 举 例 【程序6－14】 向下调整和建堆运算。 void AdjustDown (T heap[], int r, int n) { int child=2*r; T temp=heap[r]; while (child=n) { if (child n heap[child] heap[child+1]) child++; if (temp= heap[child]) break; heap[child/2]=heap[child]; child *=2; } heap[child/2]=temp; } void CreateHeap(MinHeap *hp) { int i, n=hp-Size; for (i=n/2; i0; i--) AdjustDown(hp-Elements, i, n); } 6.4.2 优先权队列 堆是实现优先权队列的有效的数据结构。如果假定最小值是最高优先权，我们使用最小堆，否则使用最大堆。这里使用最小堆。从优先权队列中删除最高优先权的元素的操作是容易实现的。由于堆顶元素是堆中具有最小值的元素，我们只需取出和删除堆顶元素即可。当然，删除堆顶元素后，必须将堆中剩余元素重新调整成堆。将新元素插入队列后，也必须重新调整，使之成为堆。 1. 优先权队列ADT 我们先来定义优先权队列的抽象数据类型，见ADT 6－2 PQueue。 ADT 6－2 PQueue{ 数据： n≥0个元素的MinHeap。 运算： void CreatePQ(PQueue * pq, int maxsize); 构造一个空优先权队列。 　　 BOOL IsEmpty(PQueue pq) 若优先权队列为空，则返回TRUE，否则返回FALSE。 BOOL IsFull(PQueue pq) 　　若优先权队列已满，则返回TRUE，否则返回FALSE。 void Append(