• 1. 1数据结构中国地质大学信息工程学院 2015年秋
  • 2. 2第五章 树
  • 3. 3内容提要5.1 树的基本概念 5.2 二叉树 5.3 二叉树的存储表示 5.4 二叉树的遍历及其应用 5.6 树与森林 5.7 树与森林的遍历及其应用 5.8 堆及其应用 5.9 Huffman树及其应用
  • 4. 4优先队列 队列:FIFO(按元素进入队列的次序); 优先队列(Priority Queue):出队列的顺序由元素的优先级决定,如: 医院中的急诊处理; 操作系统中使用优先队列进行作业调度; 事件驱动模拟处理。
  • 5. 5最大优先队列的ADTADT MaxPriorityQueue { 实例 有限的元素集合,每个元素都有一个优先权操作 Create( ):创建一个空的优先队列 Size( ):返回队列中的元素数目 Max( ):返回具有最大优先权的元素 Insert(x):将x插入队列 DeleteMax(x):从队列中给删除具有最大优先权的元素,并将该元素返回至x }
  • 6. 6优先队列的线性表实现优先队列的另一种实现方式——堆(Heap)。无序顺序表 插入在表的末尾,Θ(1) 删除时先查找优先权最大的元素,Θ(n)。无序链表 插入在链头,Θ(1) 删除时先查找优先权最大的元素,Θ(n)。有序线性表 插入时间,Θ(n) 删除时间,Θ(1)。
  • 7. 7 回顾特性6 如果将一棵有n个节点的完全二叉树自顶向下,同一层自左向右连续给节点编号1,2,…,n。设该完全二叉树中一元素的序号为i,1≤i≤n。则有下列关系成立:(2)当2i>n时,该元素无左孩子。否则,其左孩子的编号为2i;(3)若2i+1>n,该元素无右孩子。否则,其右孩子的编号为2i+1。(1)若i=1,则节点i为根,无双亲;若i>1,则节点i的双亲节点编号为 ;ABDGCFEIHJ12345678 9 10 特性5 具有n个节点的完全二叉树的深度h为 。
  • 8. 8 堆的定义 如果将此数据元素序列用一维数组存储,并将此数组对应一棵完全二叉树,则堆的含义可以理解为:在完全二叉树中任何非终端节点的值均不大于(或小于)其左、右孩子节点的值。 设有n个数据元素的值为(k0,k1,…,kn-1),如果它们满足以下的关系:ki≤k2i+1且ki≤k2i+2(或ki≥k2i+1且ki≥k2i+2)(i=0,1,…,  n-2/2  ),则称之为堆(Heap)。1.堆(Heap)
  • 9. 99172378876531534587784593153231765最小堆(MinHeap)最大堆(MaxHeap)9176523457887533187785345659311723 最小(大)堆:位于堆顶(即完全二叉树的根节点位置)的节点的值是整个序列中最小(大)的。ki≤k2i+1且ki≤k2i+2ki≥ k2i+1且ki≥k2i+2
  • 10. 10堆的元素下标计算由于堆存储在下标从 0 开始计数的一维数组中,因此在堆中给定下标为 i 的结点时 如果 i = 0,结点 i 是根结点,无双亲;否则结点 i 的父结点为结点 i/2); 如果 2i+1>n-1,则结点 i 无左子女;否则结点 i 的左子女为结点 2i+1; 如果 2i+2>n-1,则结点 i 无右子女;否则结点 i 的右子女为结点 2i+2。
  • 11. 112.堆的类定义template class MinHeap : public PQueue { //最小堆继承了(最小)优先级队列 public: MinHeap (int sz = DefaultSize); //构造函数 MinHeap (E arr[], int n); //构造函数 ~MinHeap() { delete [ ] heap; } //析构函数 bool Insert (const E& x); //将x插入堆中 bool RemoveMin(E& x); //删除堆顶元素
  • 12. 12 bool IsEmpty () const //判堆空否 { return (currentSize == 0) ? true : false; } bool IsFull () const //判堆满否 { return (currentSize == maxHeapSize) ? true : false; } void MakeEmpty () { currentSize = 0; } //置空堆 private: E *heap; //最小堆元素存储数组 int currentSize; //最小堆当前元素个数 int maxHeapSize; //最小堆最大容量 void siftDown (int start, int m); //向下调整算法[start, m] void siftUp (int start); //向上调整算法[start, 0] }
  • 13. 133.堆的建立:建立空堆template MinHeap::MinHeap (int sz) //建立空堆 { maxHeapSize = (DefaultSize < sz) ? sz : DefaultSize; heap = new E[maxHeapSize]; //创建堆空间 if (heap == NULL) { cerr << “堆存储分配失败!” << endl; exit(1); } currentSize = 0; //建立当前大小 }
  • 14. 144.堆的建立:初始化最小堆复制一个数组并对其进行调整形成一个堆。201215351080301721201235151080301221[0][1][2][3][4][5][6][7][8][9]最后一个分支节点一定是最后一个叶节点的双亲 i = (CurrentSize-2)/2
  • 15. 15201215351080301721201215351803017210
  • 16. 16201215351803017210201223518030171510
  • 17. 17201223518030171510201223018035171510
  • 18. 18201223018035171510201230108035171512
  • 19. 19201230108035171512121530108035172012
  • 20. 20template MinHeap::MinHeap (E arr[], int n) //通过数组调整形成堆 { maxHeapSize = (DefaultSize < n) ? n : DefaultSize; heap = new E[maxHeapSize]; if (heap == NULL) { cerr << “堆存储分配失败!” << endl; exit(1); } for (int i = 0; i < n; i++) heap[i] = arr[i]; currentSize = n; //复制堆数组, 建立当前大小 int currentPos = (currentSize-2)/2; //找最初调整位置:最后分支结点堆的建立:最小堆初始化
  • 21. 21 while (currentPos >= 0) { //逐步向上扩大堆 siftDown (currentPos, currentSize-1); //局部自上向下下滑调整 currentPos--; } }
  • 22. 22 最小堆的向下调整算法siftDown( ) 从结点i开始向下调整 : 比较结点i左孩子结点(2*i+1)和右孩子结点(2*i+2)的关键字的大小,沿关键字小的分支进行调整,(用j指示关键字值较小的孩子结点); 比较结点i和结点j的关键字,若结点i的关键字大于结点j的关键字,则两结点对调位置(相当于把关键字小的结点上浮); 令i=j,j=2*j+1,继续向下一层进行比较;【结束条件】若结点i的关键字不大于结点j的关键字或结点i没有孩子时调整结束。
  • 23. 23最小堆的下滑调整算法template void MinHeap::siftDown (int start, int m ) { int i = start, j = 2*i+1; //j是i的左子女位置 E temp = heap[i]; while (j <= m) //检查是否到最后位置 { if ( j < m && heap[j] > heap[j+1] ) j++; //让j指向两子女中的小者 if ( temp <= heap[j] ) break; //小则不做调整 else { heap[i] = heap[j]; i = j; j = 2*j+1; } //否则小者上移, i, j下降 } heap[i] = temp; //回放temp中暂存的元素 } 算法时间复杂度:O(log2n)
  • 24. 24最小堆的初始化函数的时间复杂性 while循环:CurrentSize-2/2 —> 0 每次所花时间:O(log2n) 循环次数:n/2 总的时间复杂度:O(nlog2n) 最好情况下,时间复杂度Ω(n) ,即数组元素按照最小堆组织。
  • 25. 25自下向上逐步调整为最小堆i = 3i = 25353171778780923456587i0923456587i书上例子:P237
  • 26. 26i = 15353171778780923456587i0923456587i
  • 27. 27i = 05353171778780923456587i0923456587i09
  • 28. 285353171778780923456587i0923456587i17
  • 29. 29课堂练习 最大堆初始化如何实现? 需要修改哪些代码?201215351080301721801715351020301221
  • 30. 305.最小堆的插入 例 在右堆中分别插入以下元素: (1)值为21; (2)值为5; (3)值为1。2101420152101420152121014515201101421520
  • 31. 31最小堆的插入算法思想(1)将数据元素插入在已经建成的最小堆后面(很可能破坏堆的性质) (2)自下而上调整,使之所在的子树成为堆: 从插入节点 i 开始,比较节点 i 的值和其双亲节点 (i-1)/2的值大小; 如果节点i的值小于其双亲节点(i-1)/2的值,则交换两节点,并使i指向其双亲节点,继续向上调整,直到i=0(i为根节点)或者节点i的值大于其双亲节点的值为止。
  • 32. 32110142152021014201511234562101411520123456示例:向最小堆中插入1
  • 33. 33template bool MinHeap::Insert (const E& x ) { //公共函数: 将x插入到最小堆中 if ( currentSize == maxHeapSize ) //堆满 { cerr << "Heap Full" << endl; return false; } heap[currentSize] = x; //插入尾部 siftUp (currentSize); //向上调整 currentSize++; //堆计数加1 return true; }最小堆的插入算法
  • 34. 34template void MinHeap::FilterUp (int start) { int j = start, i = (j-1)/2; E temp = heap[j]; while (j > 0) //沿父结点路径向上直达根 { if (heap[i] <= temp) break; //父结点值小, 不调整 else { heap[j] = heap[i]; j = i; i = (i-1)/2; } //父结点结点值大, 调整 } heap[j] = temp; //回送 } 最小堆的上滑调整算法 算法时间复杂度:O(log2n)
  • 35. 35在堆中插入新元素1153171778780923456587i0923456587j1153j1123i最小堆的向上调整书上例子:P238
  • 36. 365317117878094565870923456587j115323i2317ji
  • 37. 376.最小堆的删除从最小堆中删除具有最小值的元素: (1)将最小堆的堆顶元素(即根节点)删去; (2)把堆的最后一个元素节点移到堆顶; (3)堆的当前元素个数减1; (4)调用siftDown( )函数,从堆顶向下重新调整成堆。
  • 38. 381101421520201014215删除值为21的节点将最后一个元素填补到堆顶重新调整成为堆210142015
  • 39. 39最小堆的删除算法template bool MinHeap::RemoveMin(E& x) { if ( !currentSize ) { //堆空, 返回false cout << "Heap empty" << endl; return false; } x = heap[0]; heap[0] = heap[currentSize-1]; currentSize--; siftDown(0, currentSize-1); //自上向下调整为堆 return true; //返回最小元素 }
  • 40. 40课堂练习 最大堆的插入和删除如何实现? 需要修改哪些代码?20151421021151420102插入21连续删除21和201514102
  • 41. 417. 堆的应用:堆排序(1)将要排序的n个元素初始化为一个最大堆; (2)每次从堆中提取堆顶(即删除最大)元素; (3)各元素将按递减次序排列;492525*211608123456082525*162149136542 例
  • 42. 422525*082116491234561625*0825214913654225*1608212549123456081625*252149136542
  • 43. 43211625*082549123456081625*252149136542160825*212549123456081625*252149136542
  • 44. 44template void HeapSort(T a [ ], int n) { // 利用堆排序算法对a[0:n-1]进行排序 MaxHeap H(a, n); //初始化堆 T x; // 从最大堆中逐个抽取元素 for(int i=n-2; i>=0; i--) { H.RemoveMax(x); a[i+1]=x; } }初始化所需时间:O(nlogn) 删除所需时间:O(log2n) 堆排序的时间复杂性为:O(nlog2n)课后作业: 1)调试最大堆的类模板; 2)调试堆排序算法。
  • 45. 45本结小结 优先队列的概念 堆 堆的定义、存储 堆的插入、删除、初始化操作 应用 堆排序
  • 46. 作业46P247 5.15(逐个加入元素建立堆) P247 5.16(1)(2)(将序列调整为堆)