网站建设创新,简述网站开发具体流程,衡阳网站优化外包价格,wordpress未登录用户重定向堆和优先队列 普通队列#xff1a;FIFO#xff0c;LILO 优先队列#xff1a;出队顺序和入队顺序无关#xff0c;和优先级相关。一个典型应用就是操作系统中。动态选择优先级高的任务执行 堆的实现 最典型的堆就是二叉堆#xff0c;就像是一颗二叉树。这个堆的特点#xf… 堆和优先队列 普通队列FIFOLILO 优先队列出队顺序和入队顺序无关和优先级相关。一个典型应用就是操作系统中。动态选择优先级高的任务执行 堆的实现 最典型的堆就是二叉堆就像是一颗二叉树。这个堆的特点下图可以看出 这里以最大堆为例每一个节点都不大于其父亲节点。另外堆必须是一颗完全二叉树正因为此我们可以使用数组来存储二叉堆如下图所示给二叉堆自上而下自左到右表上序号 由图中节点序号可以看出如果某个节点的序号为k,则其左子节点的序号是2*k,右子节点的序号是2*k1,这里与通常我们数组的规定不同根节点是从1开始的不是0这也是堆的经典实现方式。不过从0开始标定也会有类似性质只是常数的变化。 下面就要实现最大堆做成一个MaxHeap 类最大堆中要存储数据为了通用性将这个类做成一个模板类。这个最大堆首先得有一个存储数据的数组在用户定义之前我们不知道数组的大小所以该数组是一个指针类型相应的会在构造函数中初始化该数组。还需要一个int型的size来表示堆中元素数量。所以堆的基本框架如下 1 templatetypename Item2 class MaxHeap{3 private:4 Item* data;5 int count;6 private:7 int shiftDown(int k){8 9 }
10 public:
11 MaxHeap(int capacity){
12 data new Item[capacity];
13 count0;
14 }
15 ~MaxHeap(){
16 delete[] data;
17 }
18
19 int size(){return count;}
20
21 bool isEmpty(){return count0;}
22 }; 向堆中添加、删除元素 添加元素 因为堆的性质我们这里要用到一个添加元素时的核心操作。、shiftUp用下面的堆具体说一下思路 因为是用数组存储的堆中的元素最初52加入的时候如第二幅图所示由于新元素的加入这个堆已经不满足最大堆的性质了我们需要根据最大堆的性质调整给52找到正确的位置如何调整呢考查52的父节点比52小违背了最大堆的性质所以交换之这样以52为根节点的子堆满足了最大堆的性质继续考查新的堆中52的父节点依然不满足最大堆的定义同样的操作继续考查直到整个堆满足最大堆的性质。那么添加元素后只需要不断调用shiftUp操作就可以了具体代码实现 1 // insert(Item)2 2 void insert(Item item){3 3 data[count1] item;4 4 count;5 5 shiftUp(count);6 6 }7 7 8 8 // shiftUp(int)9 9
10 10 void shiftDown(int k){
11 11 while(data[k/2]data[k] k1){
12 12 swap(data[k],data[k/2]);
13 13 k/2;
14 14 }
15 15 } 但是 data[count1] item; 有一个数组越界的潜在风险所以我们需要在类中再定义一个capacity的成员变量并在构造函数中使用用户指定的capacity初始化 this-capacity capacity; 并且在添加新元素之前assert一下在insert(Item)函数中第三行之前加入 assert(count1capacity); 当然更好的方法就是一旦发现capacity不足够就分配新的空间Cprimer中在讲容器的时候提到过一般是采用倍增的方法这里主要讲堆我自己也没研究过这里先Mark下以后仔细想想具体实现此处就先用这种简单的方法防止数组越界。 从堆中取出元素 Note 从堆中取出元素只能取出根节点的元素。 一旦取出对顶元素就需要调整堆使得堆这颗二叉树依然满足堆的性质。还是以图的形式给出过程。 由上面过程可以看出一旦取出堆顶元素就把堆中最后一个元素放到堆顶不断调整直到这颗二叉树再次满足最大堆的性质。这个不断调整的过程就是shiftDown 的过程。简单说一下这个过程。现在16处在堆顶位置比它的左右子节点都要小最大堆的性质要求父亲节点要大于子节点所以应该调整向左还是向右是有左右的大小决定的谁大跟谁换这样16跟52换然后再考查新的堆继续考查16直到16在它正确的位置。具体实现如下 1 //shiftDown(int);2 void shiftDown(int k){3 //int j 2*k;4 while(2*kcount){5 int j 2*k;6 if(data[j]data[j1])7 j;8 if(data[k]data[j]){9 swap(data[k],data[j]);
10 k j;
11 }
12 }
13 }
14
15 //get the top of heap Item top()
16 Item get(){
17 assert(count0);
18 Item item data[1];
19 swap(data[1],data[count])
20 count--;
21 //swap(data[])
22 shiftDown(1);
23 return item;
24 } 前面给出了取出对顶元素的方法如果不断取出堆顶元素并打印出来就是一个从大到小的数组由此可以想到利用堆进行排序这个排序接收一个数组和数组元素个数创建一个heap类的对象通过这个对象调用insert()函数和top() 函数即可实现具体实现 1 void heap_sort(int arr[],int n){
2 MaxHeapint maxHeap MaxHeap(n);
3 for(int i 0;in;i)
4 maxHeap.insert(arr[i]);
5 for(int i 0;in;i)
6 arr[i] maxHeap.top();
7 } 上面实现的是从大到小的排序要想从小到大排序反向打印就可以只需将第5行改为 for(int i n-1;i0;i--) 堆的heapify 前面提到了最大堆排序我将上面的堆排序实现方式与归并排序和快速排序时间做了一个比较前面的堆排序的方式花费的时间较长回顾一下前面的堆排序需要将数组元素一个一个的插入堆中利用堆不断的调整从堆中取出元素的时候也需要不断的调整使得二叉树依然保有最大堆的性质这种方式的效率显然不高说道这里我想起来了不断调整过程中需要不断的shiftUp和shiftDown这两个操作都需要swap()操作前面讲插入排序的时候提到过swap操作相对于移动/赋值操作是低效的所以这里也是可以改进的不过下面要说的是改进数组构成堆的方式给定一个数组我们让这个数组形成一个堆的形状这个过程叫--Heapify.还是以图片形式演示过程下图只给出了一部分过程的图示 看第一幅图右下角是一个数组将该数组构建成一颗完全二叉树但是这颗二叉树不是堆如果将这颗完全二叉树根据对的性质调整成堆那么就将数组构造成了堆调整过程就是上图示过程 看第二幅图中所有叶子节点它们本身各自就是一个堆还是以最大堆为例一个最大堆Note一颗完全二叉树第一个非叶子节点是5元素数目为10可以多举些例子可以找出规律一颗完全二叉树第一个非叶子节点是k/2取整k为完全二叉树节点个数这里是上取整并且是从1开始而不是从0开始可以证明的。现在自下而上考查非叶子节点第一个是5它的值是32以它为根的子树不满足最大堆的性质它比子节点小所以做一次shiftDown操作接着考查4位置13也比子节点小再执行一次shiftDown操作接着考查位置3也不满足继续执行shiftDown再看2 17比它的子节点小shiftDown但是调整到5上依然不满足继续shiftDown直到17在正确的位置上 这时以62为根的子树满足了最大堆性质接着向上一层树顶元素不满足shiftDown直到调整到15应该在的位置。可以构建一个构造函数接收一个数组和数组容量代码实现如下 1 MaxHeap(Item arr[],int n){
2 data new Item[n];
3 capacity n;
4 for(int i 0;in;i)
5 data[i1] arr[i];
6 count n;
7 for(int k n/2;k0;k--)
8 shiftDown(k);
9 } 使用这个构造函数进行heapsort 1 void heap_sort2(int arr[],int n){
2 MaxHeapint maxHeap MaxHeap(arr,n);
3 for(int i n-1;i0;i--)
4 arr[i] maxHeap.top();
5 } 再次测试时间性能上比前面的堆排序快但依然是比归并排序和快速排序慢不过堆排序通常用于动态数据的维护而不是系统级别的排序。 将n个元素逐个插入到一个空堆中时间复杂度是O(NlogN)的 但是heapify的过程算法复杂度是O(N)这个我没有证明。只是看书上写的 原地堆排序 前面介绍的堆排序算法都需要将数据从数组放入堆中再从堆中取出。这需要分配额外的空间但是根据堆排序的思想整个数组的排序过程可以原地进行不需要再分配额外空间。回想之前通过数组构造堆的过程可以看出一个数组其实可以把它看成一个堆因此可以将数组通过heapify过程构建成堆还是以最大堆为例。 这是一个数组形式排列的最大堆堆顶元素v为整个数组中最大的按照排序后的结果v应该在数组尾部所以将v与最后一个元素w交换交换后这个数组不再是一个最大堆橙色部分不再是最大堆如何调整成最大堆根据前面的就是不断的调用shiftDown调整成一个最大堆依然用暗红色表示该部分是最大堆蓝色表示已经排序好的。 此时又重复上面的过程继续交换v和w然后将未排序的部分调整成最大堆。 Note由于整个过程在数组上原地进行数组是从0开始索引的所以在实现的时候注意调整主要是shiftDown过程的索引具体的就是父亲节点与子节点索引的关系举个例子很容易看出来 最后一个非叶子节点同时也变成了 (count-1)/2 ,依然是上取整。 实现代码如下 1 void heapSort(int arr[],int n){2 //heapify3 // index begins with 04 // the first leaf node which is not null (count-1)/25 for(int i (n-1)/2;i0;i--)6 __shiftDown(arr,n,i);7 for(int i n-1;i0;i--){8 swap(arr[i],arr[0]);9 __shiftDown(arr,i,0);
10 }
11 }
12
13 void __shiftDown(int arr[],int n,int k){
14 while(2*k1n){
15 int j 2*k1;
16 if(arr[j]arr[j1] j1n)
17 j1;
18 if(arr[k]arr[j]){
19 swap(arr[k],arr[j]);
20 k j;
21 }
22 }
23 } 优化 之前提到过用赋值操作代替交换操作会提升时间效率在这里实现 1 void __shiftDown2(int arr[],int n,int k){2 int e arr[k];3 while(2*k1n){4 int j 2*k1;5 if(arr[j]arr[j1])6 j1;7 if(earr[j]) break;8 arr[k] arr[j];9 k j;
10 }
11 arr[k] e;
12 } 排序算法总结 到这里所有排序算法都写完了下面的图是我在GitHub上看到的关于排序算法的总结 这里有一个排序算法稳定性的概念之前没有提到过 算法稳定性对于相等的元素在排序后原来靠前的元素依然靠前相等的元素的相对位置没有发生改变 我觉得他给出的这个解释的前半句非常好理解对于算法稳定性。 转载于:https://www.cnblogs.com/Holly-blog/p/9321011.html
