第9章优先队列课件

第9章优先队列(Priority Queue)2本章内容9.1 引言9.2 线性表9.3 堆9.4 左高树9.5 应用1.堆的实现2.堆排序3.左高树4.霍夫曼编码本章重点7/12/2024349.1 引言优先队列优先队列优先队列（priority queue）是0个或多个元素的集合，每个元素都有一个优先权或值优先权或值。与FIFO结构的队列不同，优先队列中元素出队列的顺序由元素的优先级决定。从优先队列中删除元素是根据优先权高或低的次序，而不是元素进入队列的次序.对优先队列执行的操作有:1)查找一个元素2)插入一个新元素3)删除一个元素5优先队列n两种优先队列:n最小优先队列（Min priority queue）n最大优先队列（Max priority queue）n在最小优先队列最小优先队列(Min priority queue)中，“查找/删除”操作用来“搜索/删除”优先权最小优先权最小的元素；n在最大优先队列最大优先队列（Max priority queue）中，“查找/删除”操作用来“搜索/删除”优先权最大优先权最大的元素。n优先权队列中的元素可以有相同的优先权。6最大优先权队列的抽象数据类型描述抽象数据类型 MaxPriorityQueue实例例有限的元素集合，每个元素都有一个优先权操作操作 Create()：创建一个空的优先队列 Size()：返回队列中的元素数目 Max()：返回具有最大优先权的元素 Insert(x)：将x插入队列 DeleteMax(x)：从队列中删除具有最大优先权的元素，并将该元素返回至x 最小优先权队列的抽象数据类型描述?7优先队列的描述优先队列的描述线性表堆（Heaps）左高树（Leftist trees）89.2 线性表采用无序线性表描述最大优先队列公式化描述（利用公式Location(i)=i-1)插入：表的右端末尾执行，时间:(1);删除:查找优先权最大的元素，时间:(n);使用链表，插入：在链头执行，时间:(1);删除:(n);采用有序线性表描述最大优先队列公式化描述（利用公式Location(i)=i-1，元素按递增次序排列)插入:O(n);删除:O(1);使用链表（按递减次序排列）插入:O(n);删除:O(1);99.3 堆(Heaps)9.3.1 定义 定义最大树（最小树）每个节点的值都大于（小于）或等于其子节点（如果有的话）值的树。最大树或最小树节点的子节点个数可以大于2。最大（小）树7/12/20241011定义最大堆（最小堆）：最大（最小）的完全二叉树。24679386398672651712判断哪些是最大（小）堆？13堆是完全二叉树，可用一维数组有效地描述堆.986726517 9 8 7 6 7 2 6 5 1 0 1 2 3 4 5 6 7 8 9 10149.3.2 最大堆的插入9867726515 新元素是新元素是5 5159.3.2 最大堆的插入98677265120 新元素是新元素是2020169.3.2 最大堆的插入98672651720179.3.2 最大堆的插入96726517820189.3.2 最大堆的插入67265178920199.3.2 最大堆的插入插入的时间复杂性:每一层的工作，耗时：(1)实现插入策略的时间复杂性为：O(height)=O(log2n),（n 是堆的大小）209.3.3 最大堆的删除最大元素在根上。最大元素在根上。2067265171589219.3.3 最大堆的删除最大元素被删除以后最大元素被删除以后67265171589229.3.3 最大堆的删除具有具有10个节点的堆个节点的堆.在堆中重新插入在堆中重新插入8.67265171589239.3.3 最大堆的删除67265171598需要进行调整（或重构）。左子树和右子树是最大堆需要进行调整（或重构）。左子树和右子树是最大堆249.3.3 最大堆的删除67265179158259.3.3 最大堆的删除67265178159269.3.3 最大堆的删除删除的时间复杂性:删除的时间复杂性与插入的时间复杂性相同.每一层的工作，耗时：(1)实现删除策略的时间复杂性为：O(height)=O(log2n),（n 是堆的大小）279.3.4 最大堆的初始化1.通过在初始化为空的堆中执行n次插入操作来构造。O(nlog2n)更快的堆的初始化策略？2.通过必要时对树进行调整的方法构造。(n)n从第一个具有孩子的节点开始，n这个元素在数组中的位置为i=n/2n如果以这个元素为根的子树已是最大堆，则此时不需调整n否则必须调整子树使之成为堆。n随后，继续检查以i-1,i-2等节点为根的子树n直到检查到整个二叉树的根节点（其位置为1）。思想7/12/202428299.3.4 最大堆的初始化 例:输入数组=1,2,3,4,5,6,7,8,9,10,11 4678931115210309.3.4 最大堆的初始化l从数组中最右一个有孩子的节点开始l这个元素的位置 i=n/2.4106789311152319.3.4 最大堆的初始化4678931015112329.3.4 最大堆的初始化4678931015112339.3.4 最大堆的初始化4678310151129349.3.4 最大堆的初始化4678310151129359.3.4 最大堆的初始化4678310151129369.3.4 最大堆的初始化4678310151129379.3.4 最大堆的初始化467831015119为 2 找位置389.3.4 最大堆的初始化467831015119为 2 找位置399.3.4 最大堆的初始化4678321015119409.3.4 最大堆的初始化4678321015119419.3.4 最大堆的初始化467832101159为 1 找位置429.3.4 最大堆的初始化467832115109为 1 找位置439.3.4 最大堆的初始化467832511109为 1 找位置449.3.4 最大堆的初始化467832511110945初始化堆的时间复杂性初始化堆的时间复杂性:堆的高度=h.在j层节点的数目=2j-1.以j层节点为根的子树的高度=h-j+1调整（或重构）以j层节点为根的子树：O(h-j+1).调整（或重构）所有以j层节点为根的子树：=2j-1(h-j+1)=t(j).总的时间：t(1)+t(2)+t(h-1)=O(2h)=O(n).9.3.5 类MaxHeaptemplateclass MaxHeap public:MaxHeap(int MaxHeapSize=10);MaxHeap()delete heap;int Size()const return CurrentSize;T Max()if(CurrentSize=0)throw OutOfBounds();return heap1;MaxHeap&Insert(const T&x);MaxHeap&DeleteMax(T&x);void Initialize(T a,int size,int ArraySize);private:int CurrentSize,MaxSize;T*heap;/元素数组;7/12/20244647堆是完全二叉树，可用一维数组有效地描述堆.986726517 9 8 7 6 7 2 6 5 1 0 1 2 3 4 5 6 7 8 9 10currentsizeMaxsizeheap48MaxHeap构造函数templateMaxHeap:MaxHeap(int MaxHeapSize)/构造函数MaxSize=MaxHeapSize;heap=new TMaxSize+1;CurrentSize=0;最大堆的插入templateMaxHeap&MaxHeap:Insert(const T&x)/把x插入到最大堆中if(CurrentSize=MaxSize)throw NoMem();/为x寻找相应插入位置/i从新的叶节点开始，并沿着树上升int i=+CurrentSize；while(i!=1&xheapi/2)/不能把x放入heapiheapi=heapi/2;i/=2;heapi=x;return*this;7/12/202449最大堆的删除（1/2）templateMaxHeap&MaxHeap:DeleteMax(T&x)/将最大元素放入x，并从堆中删除最大元素/检查堆是否为空if(CurrentSize=0)throw OutOfBounds();/队列空x=heap1;/最大元素/重构堆T y=heapCurrentSize-;/最后一个元素/从根开始，为y寻找合适的位置int i=1,/堆的当前节点 ci=2;/i的孩子 7/12/20247/12/202450最大堆的删除（2/2）while(ci=CurrentSize)/heapci应该是i较大的孩子if(ciCurrentSize&heapci=heapci)break;/能 /不能heapi=heapci;i=ci;ci*=2;heapi=y;return*this;7/12/20245152void MaxHeap:Initialize(T a,int size,int ArraySize)/把数组a初始化为最大堆.delete heap;heap=a;CurrentSize=size;MaxSize=ArraySize;/产生一个最大堆for(int i=CurrentSize/2;i=1;i-)T y=heapi;/子树的根/寻找放置y的位置int c=2*i;/c的父节点是y的目标位置while(c=CurrentSize)/heapc 应是较大的同胞节点if(c CurrentSize&heapc=heapc)break;/能/不能heapc/2=heapc;/将孩子上移c*=2;/下移一层heapc/2=y;53Initialize(T a,int size,int ArraySize)把数组a初始化为最大堆。为避免调用堆的析构函数时将数组a删除，在MaxHeap类中增加Deactive函数。Void Deactive()heap=0;