DSA第5章堆和优先权队列.ppt

* 5.6.1 堆 1．堆的定义 （1）一个大小为n的堆（heap）是一棵包含n个结点的完全二叉树，该树中每个结点的关键字值大于等于双亲结点的关键字值。这样定义的堆称为最小堆（MinHeap）。 例如： 右图的完全二叉树 是最小堆。 0 1 2 3 4 5 堆底 堆顶 （2）堆又可以定义为： 堆是n个元素的序列（k0,k1,…,kn-1），当且仅当满足 ki? k2i+1 且ki? k2i+2, ( i=0，1,2,…,?（n-2）/2? ) 时 称为堆(最小堆)。 例如：序列 （23，53，34，65，83，74） 是最小堆。 0 1 2 3 4 5 2.堆的顺序存储表示 堆的顺序表示是完全二叉树的顺序表示。 3．向下调整和建堆运算 （1）函数 void AdjustDown(T keap[],int r,int j) 设序列以顺序方式保存在一维数组heap[]中，数组元素具有可比较大小的类型。 假定从数组中r+1到j，这j-r个位置上的元素已满足ki? k2i+1 且ki? k2i+2, ( i=0，1,2,…,?（n-2）/2? )条件，现向下调整第r位置上的元素，如果kr大于 k2r+1 和k2r+2,中的较小的元素，则将kr与该较小元素交换，继续这样的过程，直到不再需要调整，或到达堆底为止。 template class T void AdjustDown (T heap[], int r, int j) { int child; T temp=heap[r]; child=2*r+1; //child是r的左孩子 while (child=j) { if (( childj) (heap[child]heap[child+1])) child++; if (temp= heap[child]) break; heap[(child-1)/2]=heap[child]; child=2*child+1; } heap[(child-1)/2]=temp; } r 0 1 2 3 4 5 6 7 8 9 （2）建堆运算 它通过从第?n/2?位置开始，直到第一个元素，重复调用AdjustDown函数实现之。 template class T void MinHeap(T heap[],int n) { for(int i=(n-2)/2;i-1;i--) AdjustDown(heap,i,n-1); } 例 74 71 例 ： 初始序列 5.6.2 优先权队列 1．优先权队列 优先权队列不同于先进先出（FIFO）队列，优先权队列中的元素，按其优先级的高低而不是按元素进入队列的次序，来确定出队列的次序。最小值为最高优先权。从优先权队列中删除最高优先权元素来实现优先操作。 2．优先权队列的C++类 Insert：将一个新元素插入优先权队列， Delete：从队列中取出具有最高优先级的元素，并从队列中删除之。 3.优先权队列ADT ADT PrioQueue{ 数据： n=0个元素的最小堆； 运算：÷ Create() :建立一个空队列； Destroy():撤销一个队列； IsEmpty():若队列空，返回true,否则返回false; IsFull() :若队列满，返回true,否则返回false; Append(x):元素值为x的新元素插入队列； Serve(x) :在x中返回具有最高优先权的元素值，并从优先 队列中删除该元素。 }; 程序5-12 优先权队列的C++类 templateclass T class PriorityQueue { public: PriorityQueue(int mSize=20); ~PriorityQueue(){ delete[] q; }; void Append(const T x); //入队列操作 void Serve(T x); //出队列操作 bool IsEmpty() const { return n==0;} //判定队列是否为空 bool IsFull() const { return n==maxSize;} //判定队列是否满 private: void AdjustDown (int r,int