LeetCode Lect7 堆及其应用
概述 堆是一颗完全二叉树。分为大根堆(父节点>=所有的子节点)和小根堆(父节点<=所有的子节点)。 插入、删除堆顶都是O(logN),查询最值是O(1)。 ? 完全二叉树(Complete Binary Tree) 若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。 完全二叉树是由满二叉树而引出来的。对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树。 完全二叉树的特性:对于结点t,t/2为它的父节点,2*t、2*t+1为它的子节点。所以可以直接用一个线性的数组存放堆。 ? 堆的基本操作:(以小根堆为例) 1.堆元素上移:和自己的父节点比较,若满足条件则交换。再次比较。 void up(int x) { int p,q; p=x; while (p/2>=1) { q=p/2; if (a[q]>a[p]) swap(&a[p],&a[q]); else break; p=q; } } 2.堆元素下移:和自己的子节点中更满足条件(更大or更小)的一个比较,若满足条件则交换。再次比较。 void down(int x) { int p,q; p=x; while (p*2<=n) { q=2*p; if ((a[q+1]<a[q])&&(q+1<=n)) q++; if (a[q]<a[p]) swap(&a[q],&a[p]); else break; p=q; } } 3.建堆: cin>>n; for (i=1;i<=n;i++) cin>>a[i]; for (i=n/2;i>=1;i--) //1 down(i); 4.删除元素(删除堆顶的最值元素) 用堆最末端(二叉树的最右下角)的元素替换堆顶元素,n--,然后对其进行down(i)操作 ? 5.添加元素 将元素添加到堆的最末端(二叉树的最右下角),n++,然后对其进行up(i)操作 ? 6. 删除任意一个点(事先要保证堆中没有重复元素) 首先在堆中找到该元素的位置(可以提前用hashmap记录) 用堆最末端(二叉树的最右下角)的元素替换要删除的元素,n--。然后对其进行up(i)或者down(i)操作,根据元素的大小而定。 ? 注意:一个已从小到大排好序的数组是一个小根堆,但一个小根堆数组里面的元素不一定排好序?? (source:算法导论P153??? Exercise6.1-5、6.1-6) ? ? ? 题目 https://www.jiuzhang.com/solution/heapify/ ? 基于 Siftup 的版本 ?? O(NlogN) ? ? public class Solution { /** * @param A: Given an integer array * @return: void */ private void siftup(int[] A,int k) { while (k != 0) { int father = (k - 1) / 2; if (A[k] > A[father]) { break; } int temp = A[k]; A[k] = A[father]; A[father] = temp; k = father; } } public void heapify(int[] A) { for (int i = 0; i < A.length; i++) { siftup(A,i); } } } ? 算法思路: 时间复杂度分析 因此总的时间复杂度是 O(nlogn) ? ? ? 基于 Siftdown 的版本 ?? O(N) public class Solution { /** * @param A: Given an integer array * @return: void */ private void siftdown(int[] A,int k) { while (k * 2 + 1 < A.length) { int son = k * 2 + 1; // A[i] 的左儿子下标。 if (k * 2 + 2 < A.length && A[son] > A[k * 2 + 2]) son = k * 2 + 2; // 选择两个儿子中较小的。 if (A[son] >= A[k]) break; int temp = A[son]; A[son] = A[k]; A[k] = temp; k = son; } } public void heapify(int[] A) { for (int i = (A.length - 1) / 2; i >= 0; i--) { siftdown(A,i); } } } 算法思路: 时间复杂度分析 ? ? ? 堆的应用:
原理:对输入数据建堆,然后每次输出堆顶元素,然后删除堆顶元素。循环n次即可输出完排序好的n个数。 ????? 从小到大排序选小根堆,从大到小排序选大根堆。 1 #include <iostream> 2 using namespace std; 3 int a[1000]; 4 int n,i,tx; 5 6 void swap(int *a,int *b) 7 { 8 int tmp; 9 tmp=*a; 10 *a=*b; 11 *b=tmp; 12 } 13 14 void down(int x) 15 { 16 int p,q; 17 p=x; 18 while (p*2<=n) 19 { 20 q=2*p; 21 if ((a[q+1]<a[q])&&(q+1<=n)) q++; 22 if (a[q]<a[p]) 23 swap(&a[q],&a[p]); 24 else 25 break; 26 p=q; 27 } 28 } 29 30 int main() 31 { 32 cin>>n; 33 for (i=1;i<=n;i++) 34 cin>>a[i]; 35 36 for (i=n/2;i>=1;i--) 37 down(i); 38 39 tx=n; 40 for (i=1;i<=tx;i++) 41 { 42 cout<<a[1]<<" "; 43 a[1]=a[n]; 44 n--; 45 down(1); 46 } 47 cout<<endl; 48 } ? 补充:STL里的堆操作 首先,需要#include <algorithm> STL里支持4种堆操作: void? make_heap(start_pointer,end_pointer,comp) 在指定范围的数组上建堆 void? pop_heap(start_pointer,end_pointer,comp) 删除堆顶元素,然后重建堆 void? push_heap(start_pointer,end_pointer,comp) 假设数组区间a[start]……a[end-1]已经是一个堆,然后将a[end]作为要入堆的新元素加进去,使得a[start]……a[end]是一个堆 void? sort_heap(start_pointer,end_pointer,comp) 假设数组区间a[start]……a[end-1]已经是一个堆,然后对其中的序列进行排序(排序后就不是一个有效堆了>_<) 注释:start_pointer、end_pointer分别表示起始位置、终止位置的指针 (调用方法示例:make_heap(&number[0],&number[12],cmp); ) cmp为比较函数(若不指定,默认建大根堆) ? Sample from MSDN_1996: Program Output is:(大根堆) Original array: Numbers { 4 10 70 10 30 69 96 100? } After calling make_heap Numbers { 100 30 96 10 4 69 70 10? } After calling sort_heap Numbers { 4 10 10 30 69 70 96 100? } After calling push_heap and make_heap: (事先加入了一个新元素7) Numbers { 100 69 96 30 4 70 10 10 7 ?} After calling pop_heap Numbers { 96 69 70 30 4 7 10 10 ?100 ?}? ?(此时100已不再属于堆) ? 1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 bool comp(int a,int b) //用于建小根堆的比较函数 6 { 7 return a>b; 8 } 9 10 int main() 11 { 12 int i; 13 int a[10]={0,30,96,10,4,69,70,100}; 14 //a[1..8] 15 for (i=1;i<=8;i++) 16 cout<<a[i]<<" "; 17 cout<<endl; 18 //输出原数组:30 96 10 4 69 70 10 100 19 make_heap(&a[1],&a[9]); //注意:必须多留一个空,我也不知道为什么… >_< 20 for (i=1;i<=8;i++) //比如说,对a[1…8]操作就得写成(&a[1],&a[9]) 21 cout<<a[i]<<" "; //我知道为什么啦:^_^ 22 cout<<endl; //在C语言中,数组a[1..8]这一区段的开头是a[1],但结尾是a[9] 23 //而STL中要求调用的就是数组开头和结尾,所以要多一位。 24 //比如说有long a[1000],那么数组区段其实是a[0..999] 25 //(因为C是从0开始计),而数组结尾就是a[1000],尽管a[1000]实际上无意义。 26 //输出大根堆[1..8]:100 96 70 30 69 10 10 4 27 make_heap(&a[1],&a[9],comp); 28 for (i=1;i<=8;i++) 29 cout<<a[i]<<" "; 30 cout<<endl; 31 //输出小根堆[1..8]:4 30 10 96 9 10 70 100 32 a[9]=8; 33 push_heap(&a[1],&a[10],comp); 34 for (i=1;i<=9;i++) 35 cout<<a[i]<<" "; 36 cout<<endl; 37 //a[1..9] 38 //插入一个元素8,然后输出小根堆[1..9]:4 8 10 30 69 10 70 100 96 39 pop_heap(&a[1],comp); 40 for (i=1;i<=9;i++) 41 cout<<a[i]<<" "; 42 cout<<endl; 43 //a[1..8] 44 //删除堆顶元素4,然后输出小根堆[1..8]:8 30 10 96 69 10 70 100 4 45 //(4在堆外,已经不是堆里面的元素了) 46 } 总结:堆相关题目的核心算法 Solution:根据要求建堆,然后取堆顶作为答案输出,然后由堆顶下一步扩展出新元素再次入堆 ? 题目: POJ2442 采用以下算法都可以实现在m个数中取前n小的数: 快速排序:最慢???? 手写堆:快???? 用STL堆:目测还能再快一点 另外注意一个问题:过大的数组也会影响运行速度 渣渣表示这种水题竟然写了三种版本才过….. >_< Ver1.0:用快排,最好想的算法 ?? 本来算法就不快,空间复杂度O(n*n)又太大,也影响速度。 ?? 设目前已经处理到了第i列,那么将第i列中的元素与第i+1列中的元素分别相加,得到了n*n个元素。将这些元素记录到一个数组中,快排取前n小的n个数,并记录到数组heap[1..n]中。再用heap数组中的元素与第i+2列操作,……直到处理完m列输出heap数组即可。 这么渣渣的算法当然TLE啦……→_→ Ver2.0:用手动堆 参考http://blog.csdn.net/c0de4fun/article/details/7312831 算法快了不少,空间复杂度也降到了O(n) ? 不过我写的貌似有问题……WA了 Ver3.0:直接用STL堆操作 ??????? STL支持四种堆操作:新元素入堆、弹出堆顶、建堆、排序。(见 堆及其应用.docx) ????? ??首先还和刚才一样,把第一行排序后记录到a[1..n]数组中,第二行排序后记录到b[1..n]数组中。 ??????? 然后,为了节省空间,我们不能再简单的将a[1..n]、b[1..n]分别相加了,而是这样: ??????? 因为b[1]一定是b[1..n]里最小的,所以先将a[1..n]+b[1]得到的这n个元素加入一个大根堆heap。然后再a[1..n]+b[2..n]分别相加,而对于这n(n-1)个元素,判断如果a[k]*b[j]小于堆顶元素heap[1],则弹出堆顶,然后将a[k]*b[j]加入堆。处理完这一行之后将heap中的n个元素从小到大记录到数组a中,再将下一行读入b[1..n]中。以此类推,直到m行处理完。 ??????? AC!^_^ ? POJ2051 一次AC!??? ^_^ 题真心不难。 首先将所有的进程读入,记录period[i]为Q_num为i的进程的周期,tm[i]为Q_num为i的进程已经运行过的次数(初始都为1)。 构造一个小根堆记录进程heap[i]=period[j]*tm[j]。一开始将所有的进程都入堆。然后取堆顶元素输出,并将堆顶元素的tm[j]++,之后再将period[j]*tm[j]再次入堆并调整。这样输出k次即可。 注意:如果在堆的调整中需要比较多个关键字(比如本题中Q_num和发生时间都是关键字),那么STL就不能用了,只能手写T^T……方法类比双关键字快速排序即可 ? ---恢复内容结束--- (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |