数据结构算法与应用语言描述

《数据结构算法与应用语言描述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构、算法与应用C++描述史玉良liangyus@sdu.edu.cn堆(Heaps)左高树(LeftistTrees)Chapter9PriorityQueuesFocus堆的实现1堆排序2左高树3霍夫曼编码4与FIFO结构的队列不同，优先队列中元素出队列的顺序由元素的优先级决定。从优先队列中删除元素是根据优先权高或低的次序，而不是元素进入队列的次序。例-CPU调度优先队列优先队列是0个或多个元素的集合，每个元素都有一个优先权或值。对优先队列执行的操作有：查找插入一个新元素删除优先队列描述最大优先队列最简单的方法是采用无序线性表。假设有一个具有n个元素的优先队列，插入

2、操作可以十分容易地在表的右端末尾执行，插入所需时间为Θ(1)。删除操作时必须查找优先权最大的元素，即在未排序的n个元素中查找具有最大优先权的元素，所以删除操作所需时间为Θ(n)。优先队列的线性表描述如果利用链表，插入操作在链头执行，时间为Θ(1)，而每个删除操作所需时间为Θ(n)。优先队列的线性表描述另一种描述方法是采用有序线性表，当使用公式化描述时元素按递增次序排列，使用链表时则按递减次序排列，这两种描述方法的删除时间均为Θ(1)，插入操作所需时间为Θ(n)。优先队列的线性表描述定义：每个节点的值都大于或等于其子节点（如果有的话）值的树。最大树最大树定义：每个节点的值都小

3、于或等于其子节点（如果有的话）值的树。最小树最小树定义：最大（最小）的完全二叉树。最大堆(最小堆)最大堆的插入插入时间复杂性插入策略从叶到根只有单一路径，每一层的工作需耗时Θ(1)，因此实现此策略的时间复杂性为O(height)=O(log2n)。最大堆的删除最大堆的删除删除时间复杂性删除策略产生了一条从堆的根节点到叶节点的单一路径，每层工作需耗时Θ(1)，因此实现此策略的时间复杂性为O(height)=O(log2n)。开始时堆中已经含有n(n>0)个元素。可以通过在初始为空的堆中执行n次插入操作来构建非空的堆，插入操作所需总时间为O(nlogn)。最大堆的初始化更快的堆

4、的初始化策略？思考从第一个具有孩子的节点开始，这个元素在数组中的位置为i=[n/2]，如果以这个元素为根的子树已是最大堆，则此时不需调整，否则必须调整子树使之成为堆。随后，继续检查以i-1,i-2等节点为根的子树，直到检查到整个二叉树的根节点（其位置为1）。思想最大堆的初始化最大堆的初始化类MaxHeaptemplateclassMaxHeap{public:MaxHeap(intMaxHeapSize=10);~MaxHeap(){delete[]heap;}intSize()const{returnCurrentSize;}TMax(){if(Curre

5、ntSize==0)throwOutOfBounds();returnheap[1];}MaxHeap&Insert(constT&x);MaxHeap&DeleteMax(T&x);voidInitialize(Ta[],intsize,intArraySize);private:intCurrentSize,MaxSize;T*heap;//元素数组};最大堆的插入templateMaxHeap&MaxHeap::Insert(constT&x){//把x插入到最大堆中if(CurrentSize==MaxSize)throwNo

6、Mem();//为x寻找相应插入位置//i从新的叶节点开始，并沿着树上升inti=++CurrentSize；while(i!=1&&x>heap[i/2]){//不能把x放入heap[i]heap[i]=heap[i/2];i/=2;}heap[i]=x;return*this;}最大堆的删除templateMaxHeap&MaxHeap::DeleteMax(T&x){//将最大元素放入x，并从堆中删除最大元素//检查堆是否为空if(CurrentSize==0)throwOutOfBounds();//队列空x=heap[1];//最大元素

7、//重构堆Ty=heap[CurrentSize--];//最后一个元素//从根开始，为y寻找合适的位置inti=1,//堆的当前节点ci=2;//i的孩子最大堆的删除while(ci<=CurrentSize){//heap[ci]应该是i较大的孩子if(ci=heap[ci])break;//能//不能heap[i]=heap[ci];i=ci;ci*=2;}heap[i]=y;return*