面试（29）
Algorithm笔试（33）
Top K 算法详解 &另参见
应用场景：
&&&&&&&&搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
&&&&&&& 假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
必备知识：
什么是哈希表？
&&&&&&& 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。
&&&&&&& 也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
&&&&&& 而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。
问题解析：
要统计最热门查询，首先就是要统计每个Query出现的次数，然后根据统计结果，找出Top 10。所以我们可以基于这个思路分两步来设计该算法。
即，此问题的解决分为以下俩个步骤：
&&&&&&& Query统计有以下俩个方法，可供选择：
&&&&&&&&1、直接排序法 & (经常在日志文件中统计时，使用cat file|format key|sort | uniq -c | sort -nr | head -n 10，就是这种方法)
&&&&&&& 首先我们最先想到的的算法就是排序了，首先对这个日志里面的所有Query都进行排序，然后再遍历排好序的Query，统计每个Query出现的次数了。
但是题目中有明确要求，那就是内存不能超过1G，一千万条记录，每条记录是255Byte，很显然要占据2.375G内存，这个条件就不满足要求了。
让我们回忆一下数据结构课程上的内容，当数据量比较大而且内存无法装下的时候，我们可以采用外排序的方法来进行排序，这里我们可以采用归并排序，因为归并排序有一个比较好的时间复杂度O(NlogN)。
排完序之后我们再对已经有序的Query文件进行遍历，统计每个Query出现的次数，再次写入文件中。
综合分析一下。
算法一：普通排序&&&&&&&&&&&& （我们只用找出top10，所以全部排序有冗余）
如果选择像快速排序，堆排序这样全排序的时间复杂度是O(NlogN)，而遍历的时间复杂度是O(N)，因此该算法的总体时间复杂度就是O(N+NlogN)=O（NlogN）。
&算法二：部分排序&
上面的算法对整个数组都进行了排序，而原题目只要求最大的K个元素，并不需要前K个数有序，也不需要后N-K个元素有序。如何避免做后N-K个数的排序呢？我们选择部分排序算法。像：选择排序，交换排序找出top k个元素的时间复杂度为O(NK)。而遍历的时间复杂度是O(N)，因此该算法的总体时间复杂度就是O(N+NK)=O（NK）。
&&&&&&&2、Hash Table法&&&&&&&&&&&&&&& (这种方法统计字符串出现的次数非常好)
&&&&&&&在第1个方法中，我们采用了排序的办法来统计每个Query出现的次数，时间复杂度是N*logN，那么能不能有更好的方法来存储，而时间复杂度更低呢？
&&&&&&&题目中说明了，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query 255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash Table绝对是我们优先的选择，因为Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。
&&&&&&&那么，我们的算法就有了：
&&&&&&&&&&&&&&&维护一个Key为Query字串，Value为该Query出现次数的HashTable，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理。
&&&&&&&&&&&&&&& 本方法相比算法1：在时间复杂度上提高了一个数量级，为O（N），但不仅仅是时间复杂度上的优化，该方法只需要IO数据文件一次，而算法1的IO次数较多的，因此该算法2比算法1在工程上有更好的可操作性。
&&&&&算法一：普通排序&&&&&&&&&&&& （我们只用找出top10，所以全部排序有冗余）
&&&& 我想对于排序算法大家都已经不陌生了，这里不在赘述，我们要注意的是排序算法的时间复杂度是NlogN，在本题目中，三百万条记录，用1G内存是可以存下的。
&&&&&算法二：部分排序&&&&&&&&&
&&&& 题目要求是求出Top 10，因此我们没有必要对所有的Query都进行排序，我们只需要维护一个10个大小的数组，初始化放入10个Query，按照每个Query的统计次数由大到小排序，然后遍历这300万条记录，每读一条记录就和数组最后一个Query对比，如果小于这个Query，那么继续遍历，否则，将数组中最后一条数据淘汰(还是要放在合适的位置，保持有序。)，加入当前的Query，对数组的十个数据排序。最后当所有的数据都遍历完毕之后，那么这个数组中的10个Query便是我们要找的Top10了。
&&&&& 不难分析出，这样，算法的最坏时间复杂度是N*K， 其中K是指top多少。（只对k个元素排序，可选择部分排序算法。用选择排序，或者冒泡排序，时间复杂度也是O(N*K)）
&&&&&&&算法三：堆
&&&&&& 在算法二中，我们已经将时间复杂度由NlogN优化到N*K，不得不说这是一个比较大的改进了，可是有没有更好的办法呢？
&&&&&& 分析一下，在算法二中，每次比较完成之后，需要的操作复杂度都是K，因为要把元素插入到一个线性表之中，而且采用的是顺序比较。这里我们注意一下，该数组是有序的，一次我们每次查找的时候可以采用二分的方法查找，这样操作的复杂度就降到了logK，可是，随之而来的问题就是数据移动，因为移动数据次数增多了。不过，这个算法还是比算法二有了改进。
&&&&&&&基于以上的分析，我们想想，有没有一种既能快速查找，又能快速移动元素的数据结构呢？
&&&&&&&回答是肯定的，那就是堆。
&&&&&& 借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此到这里，我们的算法可以改进为这样，维护一个K(该题目中是10)大小的小顶堆，然后遍历300万的Query，分别和根元素进行比较。
思想与上述算法二一致，只是在算法三，我们采用了最小堆这种数据结构代替数组，把查找目标元素的时间复杂度有O（K）降到了O（logK）。
&&&&&& 那么这样，采用堆数据结构，算法三，最终的时间复杂度就降到了N*logK，和算法二相比，又有了比较大的改进。
堆用一个数组h[ ]表示，它的父节点为h[i/2],儿子节点是h[2*i+1]和h[2*i+2].
代码如下：
if（x&h[0])//如果当前数比小顶堆顶部元素大&
& & h[0]=x;
while(p&k)
q=2*p+1;//当前根节点的左子节点。&
if(q&=k)//没有孩子节点 （孩子节点编号超过k）&
if((q&k-1)&&(h[q+1]&h[q]))//如果当前根节点的右子节点比左子节点小&
& q=q+1;
& &if(h[q]&h[p])//如何孩子节点中最小的一个比父节点小，进行堆调整。&
& & t=h[p];
& & h[p]=h[q];
& & h[q]=t;
至此，算法就完全结束了，经过上述第一步、先用Hash表统计每个Query出现的次数，O（N）；然后第二步、采用堆数据结构找出Top 10，N*O（logK）。所以，我们最终的时间复杂度是：O（N） + N'*O（logK）。（N为1000万，N’为300万）。&
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
& & & &&找出一个无序数组里面前K个最大数
算法思想1：
& & & &对数组进行降序全排序，然后返回前K个元素，即是需要的K个最大数。
&&&&&&&排序算法的选择有很多，考虑数组的无序性，可以考虑选择快速排序算法，其平均时间复杂度为O(NLogN)。具体代码实现可以参见相关数据结构与算法书籍。
算法思想2(比较好)：
& & & &&&观察第一种算法，问题只需要找出一个数组里面前K个最大数，而第一种算法对数组进行全排序，不单单找出了前K个最大数，更找出了前N(N为数组大小)个最大数，显然该算法存在“冗余”，因此基于这样一个原因，提出了改进的算法二。&
& & & & &首先建立一个临时数组，数组大小为K，从N中读取K个数，降序全排序(排序算法可以自行选择，考虑数组的无序性，可以考虑选择快速排序算法)，然后依次读入其余N
- K个数进来和第K名元素比较，大于第K名元素的值则插入到合适位置，数组最后一个元素溢出，反之小于等于第K名元素的值不进行插入操作。只待循环完毕返回临时数组的K个元素，即是需要的K个最大数。同算法一其平均时间复杂度为O(KLogK + (N - K))。具体代码实现可以自行完成。
& & & &有1亿个浮点数，请找出其中最大的10000个。
& & & &提示：假设每个浮点数占4个字节，1亿个浮点数就要站到相当大的空间，因此不能一次将全部读入内存进行排序。
& & & &可以发现如果一次读入那么机器的内存肯定是受不了的，因此我们只有想其他方法解决，解决方式为了高效还是得符合一定的该概率解决，结果并不一定准确，但是应该可以作对大部分的数据。
算法思想1、
& & & &1、我们可以把1亿个浮点数利用哈希分为了1000个组(将相同的数字哈希到同一个数组中)；
& & & &2、第一次在每个组中找出最大的1W个数，共有1000个；
& & & &3、第二次查询的时候就是100W个数中再找出最大的1W个数。
& & & &PS:100W个数中再找出最大的1W个数用类似快排的思想搞定。
算法思想2(比较好)、
& & & 1、读入的头10000个数，直接创建二叉排序树。O(1)
& & & 2、对以后每个读入的数，比较是否比前10000个数中最小的大。(N次比较)如果小的话接着读下面的数。O(N)
& & & 3、如果大，查找二叉排序树，找到应当插入的位置。
& & & &4、删除当前最小的结点。
& & & &5、重复步骤2，直到10亿个数全都读完。
& & & &6、按照中序遍历输出当前二叉排序树中的所有10000个数字。
& & & &基本上算法的时间复杂度是O(N)次比较
& & & &算法的空间复杂度是10000(常数)
& & & &基于上面的想法，可以用最小堆来实现，这样没加入一个比10000个树中最小的数大时的复杂度为log10000.
相关类似问题：
1、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
&&&& 方案1：这题是考虑时间效率。用trie树(前缀树)统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度）。然后是找出出现最频繁的前10个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的哪一个。
2、 一个文本文件，找出前10个经常出现的词，但这次文件比较长，说是上亿行或十亿行，总之无法一次读入内存，问最优解。
&&&&&方案1：首先根据用hash并求模，将文件分解为多个小文件，对于单个文件利用上题的方法求出每个文件件中10个最常出现的词。然后再进行归并处理，找出最终的10个最常出现的词。
3、 100w个数中找出最大的100个数。
方案1：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后一次扫描剩余的元素x，与排好序的100个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。依次循环，知道扫描了所有的元素。复杂度为O(100w*100)。方案2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比100多的时候，采用传统排序算法排序，取前100个。复杂度为O(100w*100)。方案3：在前面的题中，我们已经提到了，用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：118824次
积分：1867
积分：1867
排名：第19752名
原创：23篇
转载：315篇
评论：15条
(5)(10)(2)(1)(6)(4)(5)(3)(6)(26)(48)(49)(44)(102)(28)2016年11月 VB大版内专家分月排行榜第二2016年1月 MS-SQL Server大版内专家分月排行榜第二2015年12月 MS-SQL Server大版内专家分月排行榜第二2015年11月 MS-SQL Server大版内专家分月排行榜第二2015年5月 MS-SQL Server大版内专家分月排行榜第二2015年4月 MS-SQL Server大版内专家分月排行榜第二2015年1月 VB大版内专家分月排行榜第二2015年1月 MS-SQL Server大版内专家分月排行榜第二2014年12月 VB大版内专家分月排行榜第二2014年11月 MS-SQL Server大版内专家分月排行榜第二2014年9月 MS-SQL Server大版内专家分月排行榜第二2013年8月 VB大版内专家分月排行榜第二2013年6月 VB大版内专家分月排行榜第二2013年5月 VB大版内专家分月排行榜第二2010年4月 VB大版内专家分月排行榜第二2010年3月 VB大版内专家分月排行榜第二2008年12月 VB大版内专家分月排行榜第二2008年8月 VB大版内专家分月排行榜第二2008年7月 VB大版内专家分月排行榜第二2007年11月 VB大版内专家分月排行榜第二
2017年1月 MS-SQL Server大版内专家分月排行榜第三2015年6月 MS-SQL Server大版内专家分月排行榜第三2015年3月 MS-SQL Server大版内专家分月排行榜第三2015年2月 MS-SQL Server大版内专家分月排行榜第三2014年12月 MS-SQL Server大版内专家分月排行榜第三2014年10月 VB大版内专家分月排行榜第三2014年10月 MS-SQL Server大版内专家分月排行榜第三2014年8月 MS-SQL Server大版内专家分月排行榜第三2013年9月 VB大版内专家分月排行榜第三2013年3月 VB大版内专家分月排行榜第三2012年5月 VB大版内专家分月排行榜第三2012年4月 VB大版内专家分月排行榜第三2010年10月 VB大版内专家分月排行榜第三2010年8月 VB大版内专家分月排行榜第三2010年7月 VB大版内专家分月排行榜第三2009年5月 VB大版内专家分月排行榜第三2008年9月 VB大版内专家分月排行榜第三2008年4月 VB大版内专家分月排行榜第三2008年2月 VB大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。用堆排序寻找数组中最大的K个数
/***********************************************************************************
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：
即子结点的键值或索引总是小于（或者大于）它的父节点。
通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：
父节点i的左子节点在位置 (2*i+1);
父节点i的右子节点在位置 (2*i+2);
子节点i的父节点在位置 floor((i-1)/2);
在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作：
最大堆调整（Min_Heapify）：将堆的末端子结点作调整，使得子结点永远小于父结点
创建最大堆（Build_Min_Heap）：将堆所有数据重新排序
注：堆排序不是一种稳定排序。
用小根堆得办法寻找最大的K个数
用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中的最小的一个。
每次扫描一个数据X，如果X比堆顶元素Y小，则不需要改变原来的堆。如果X比堆顶元素大，
那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质。
调整过程时间复杂度为O(logK)。 全部的时间复杂度为O(N*logK)。
这种方法当数据量比较大的时候，比较方便。因为对所有的数据只会遍历一次，
*************************************************************************************/&
#include &cmath&&&
#include&cstdlib&&&
#include&time.h&&&
#include&cstdio&&&
#include&iostream&&&
//产生随机数组&&
void Random(int a[],int n)&
&&& int i=0;&
&&& srand( (unsigned)time( NULL ) );&
&&& while(i&n)&
&&&&&&& a[i++]=rand()/999;&
void print(int a[], int len)&
&&& for (i = 0; i & i++)&
&&& printf(&%6d&& &, a[i]);&
&&& printf(&\n&);&
int parent(int);&
int left(int);&
int right(int);&
void Min_Heapify(int [], int, int);&
void Build_Min_Heap(int A[],int size);&
void HeapSort(int [], int);&
/*求父亲*/&
int parent(int i)&
&&& return (int)floor((i - 1) / 2);&
/*求左孩子*/&
int left(int i)&
&&& return (2 * i + 1);&
/*求右孩子*/&
int right(int i)&
&&& return (2 * i + 2);&
/*调整堆使其满足堆得性质*/&
void Min_Heapify(int A[], int i, int heap_size)&
&&& int l = left(i);&
&&& int r = right(i);&
&&& /*找到父亲 左孩子 右孩子 之间的最大值*/&
&&& if(l & heap_size && A[l] & A[i])&
&&&&&&& least =&
&&&&&&& least =&
&&& if(r & heap_size && A[r] & A[least])&
&&&&&&& least =&
&&& /*如果父亲不是最大的，则把父亲和两个孩子的较大值交换*/&
&&& if(least != i)&
&&&&&&& temp = A[i];&
&&&&&&& A[i] = A[least];&
&&&&&&& A[least] =&
&&&&&&& /*交换之后破坏了较大孩子的堆得性质，对其进行调整*/&
&&&&&&& Min_Heapify(A, least, heap_size);&
/*简历大顶堆*/&
void Build_Min_Heap(int A[],int size)&
&&& /* 因为数组A[0]要存放数据 所以左孩子为2*i+1 右孩子为 2*i+2 */&
&&& /*取最后一个飞叶子节点&& 即堆顶& 根节点
&&& 0 1 2 -&mid=1=3/2&&& n/2
&&& 0 1 2 3 -&mid=2=4/2&&&& n/2
&&& 0 1 2 3 4 -&mid=2=5/2&& n/2
&&& 0 1 2 3 4 5 -&mid=3=6/2 n/2& 取中间元素偏右的为根节点使其成为完全二叉树
&&& int begin = size/2 ;& // 堆顶元素&&
&&& for(int i = i &= 0; i--)&
&&&&&&& Min_Heapify(A, i, size);&
/*堆排序开始*/&
void HeapSort(int A[], int heap_size)&
&&& Build_Min_Heap(A,heap_size);&
&&& //建立大顶堆之后 堆顶已经是所有元素中最大的了&&
&&& //a[0]是数组的第一个元素 a[heap_size - 1]是数组的最后一个元素&&
&&& /*将堆顶依次和最后一个叶子节点交换*/&
&&& for(int i = heap_size - 1; i &= 0; i--)&
&&&&&&& temp = A[0];&
&&&&&&& A[0] = A[i];&
&&&&&&& A[i] =&
&&&&&&& //交换之后破坏了堆得性质 重新调整&&
&&&&&&& Min_Heapify(A, 0, i);& //i 是元素个数& 每交换依次元素就少一个&&
void TopK(int arr[],int n,int K)&
&&& if(n&K)&
&&&&&&& cout&&&error&&&&
&&& int *heap=new int[K];&
&&& //随机将前K个数装入数组构建小顶堆&&
&&& for(int i=0;i&K;i++)&
&&&&&&& heap[i]=arr[i];&
&&& Build_Min_Heap(heap,K);//建立最小堆&&
&&& //从生下的数中找比小顶堆堆顶大的数并与堆顶交换(直接放在堆顶位置不交换效率更高)&&
&&& for(int i=K;i&n;i++)&
&&&&&&& if(arr[i]&heap[0])&
&&&&&&& {&
&&&&&&&&&&& heap[0]=arr[i];&
&&&&&&&&&&& //破坏了最小对的性质 对最小对进行调整&&
&&&&&&&&&&& Min_Heapify(heap,0,K);&
&&&&&&& }&
&&& for(int i=0;i&K;i++)&
&&&&&&& cout&&heap[i]&&' ';&
&&& delete []&
int main()&
&&& int a[30] = {0};&
&&& Random(a,30);&
&&& print(a,30);&
&&& cout&&endl&&&------------------------------------&&&&
&&& TopK(a,30,5);&
&&& cout&&endl&&&------------------------------------&&&&
&&& HeapSort(a,30);&
&&& cout&&endl&&&-----------------------------------&&&&
&&& print(a,30);&
&&& return 0;&
/******************
&&&& 21&&&&&&& 0&&&&&&& 7&&&&&& 26&&&&&& 10&&&&&& 11&&&&&& 23&&&&&& 10&&&&&&& 4
&&&&& 1&&&&&& 23&&&&&&& 3&&&&&& 10&&&&&& 25&&&&&& 31&&&&&& 31&&&&&& 17&&&&&& 28
&&&&& 11&&&&&& 31&&&&&& 27&&&&&& 23&&&&&& 19&&&&&&& 7&&&&&& 19&&&&&& 21&&&&&& 20
&&&&&&& 6&&&&&& 18&&&&&& 14
------------------------------------
27 28 31 31 31
------------------------------------
-----------------------------------
&&& 31&&&&&& 31&&&&&& 31&&&&&& 28&&&&&& 27&&&&&& 26&&&&&& 25&&&&&& 23&&&&&& 23
&&&& 23&&&&&& 21&&&&&& 21&&&&&& 20&&&&&& 19&&&&&& 19&&&&&& 18&&&&&& 17&&&&&& 14
&&&&& 11&&&&&& 11&&&&&& 10&&&&&& 10&&&&&& 10&&&&&&& 7&&&&&&& 7&&&&&&& 6&&&&&&& 4
&&&&&&& 3&&&&&&& 1&&&&&&& 0
Process returned 0 (0x0)&& execution time : 0.030 s
Press any key to continue.
*******************/&
/***********************************************************************************
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：
即子结点的键值或索引总是小于（或者大于）它的父节点。
通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：
父节点i的左子节点在位置 (2*i+1);
父节点i的右子节点在位置 (2*i+2);
子节点i的父节点在位置 floor((i-1)/2);
在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作：
最大堆调整（Min_Heapify）：将堆的末端子结点作调整，使得子结点永远小于父结点
创建最大堆（Build_Min_Heap）：将堆所有数据重新排序
注：堆排序不是一种稳定排序。
用小根堆得办法寻找最大的K个数
用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中的最小的一个。
每次扫描一个数据X，如果X比堆顶元素Y小，则不需要改变原来的堆。如果X比堆顶元素大，
那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质。
调整过程时间复杂度为O(logK)。 全部的时间复杂度为O(N*logK)。
这种方法当数据量比较大的时候，比较方便。因为对所有的数据只会遍历一次，
*************************************************************************************/
#include &cmath&
#include&cstdlib&
#include&time.h&
#include&cstdio&
#include&iostream&
//产生随机数组
void Random(int a[],int n)
&&& int i=0;
&&& srand( (unsigned)time( NULL ) );
&&& while(i&n)
&&&&&&& a[i++]=rand()/999;
void print(int a[], int len)
&&& for (i = 0; i & i++)
&&& printf(&%6d&& &, a[i]);
&&& printf(&\n&);
int parent(int);
int left(int);
int right(int);
void Min_Heapify(int [], int, int);
void Build_Min_Heap(int A[],int size);
void HeapSort(int [], int);
/*求父亲*/
int parent(int i)
&&& return (int)floor((i - 1) / 2);
/*求左孩子*/
int left(int i)
&&& return (2 * i + 1);
/*求右孩子*/
int right(int i)
&&& return (2 * i + 2);
/*调整堆使其满足堆得性质*/
void Min_Heapify(int A[], int i, int heap_size)
&&& int l = left(i);
&&& int r = right(i);
&&& /*找到父亲 左孩子 右孩子 之间的最大值*/
&&& if(l & heap_size && A[l] & A[i])
&&&&&&& least =
&&&&&&& least =
&&& if(r & heap_size && A[r] & A[least])
&&&&&&& least =
&&& /*如果父亲不是最大的，则把父亲和两个孩子的较大值交换*/
&&& if(least != i)
&&&&&&& temp = A[i];
&&&&&&& A[i] = A[least];
&&&&&&& A[least] =
&&&&&&& /*交换之后破坏了较大孩子的堆得性质，对其进行调整*/
&&&&&&& Min_Heapify(A, least, heap_size);
/*简历大顶堆*/
void Build_Min_Heap(int A[],int size)
&&& /* 因为数组A[0]要存放数据 所以左孩子为2*i+1 右孩子为 2*i+2 */
&&& /*取最后一个飞叶子节点&& 即堆顶& 根节点
&&& 0 1 2 -&mid=1=3/2&&& n/2
&&& 0 1 2 3 -&mid=2=4/2&&&& n/2
&&& 0 1 2 3 4 -&mid=2=5/2&& n/2
&&& 0 1 2 3 4 5 -&mid=3=6/2 n/2& 取中间元素偏右的为根节点使其成为完全二叉树
&&& int begin = size/2 ;& // 堆顶元素
&&& for(int i = i &= 0; i--)
&&&&&&& Min_Heapify(A, i, size);
/*堆排序开始*/
void HeapSort(int A[], int heap_size)
&&& Build_Min_Heap(A,heap_size);
&&& //建立大顶堆之后 堆顶已经是所有元素中最大的了
&&& //a[0]是数组的第一个元素 a[heap_size - 1]是数组的最后一个元素
&&& /*将堆顶依次和最后一个叶子节点交换*/
&&& for(int i = heap_size - 1; i &= 0; i--)
&&&&&&& temp = A[0];
&&&&&&& A[0] = A[i];
&&&&&&& A[i] =
&&&&&&& //交换之后破坏了堆得性质 重新调整
&&&&&&& Min_Heapify(A, 0, i);& //i 是元素个数& 每交换依次元素就少一个
void TopK(int arr[],int n,int K)
&&& if(n&K)
&&&&&&& cout&&&error&&&
&&& int *heap=new int[K];
&&& //随机将前K个数装入数组构建小顶堆
&&& for(int i=0;i&K;i++)
&&&&&&& heap[i]=arr[i];
&&& Build_Min_Heap(heap,K);//建立最小堆
&&& //从生下的数中找比小顶堆堆顶大的数并与堆顶交换(直接放在堆顶位置不交换效率更高)
&&& for(int i=K;i&n;i++)
&&&&&&& if(arr[i]&heap[0])
&&&&&&&&&&& heap[0]=arr[i];
&&&&&&&&&&& //破坏了最小对的性质 对最小对进行调整
&&&&&&&&&&& Min_Heapify(heap,0,K);
&&& for(int i=0;i&K;i++)
&&&&&&& cout&&heap[i]&&' ';
&&& delete []
int main()
&&& int a[30] = {0};
&&& Random(a,30);
&&& print(a,30);
&&& cout&&endl&&&------------------------------------&&&
&&& TopK(a,30,5);
&&& cout&&endl&&&------------------------------------&&&
&&& HeapSort(a,30);
&&& cout&&endl&&&-----------------------------------&&&
&&& print(a,30);
&&& return 0;
/******************
&&&& 21&&&&&&& 0&&&&&&& 7&&&&&& 26&&&&&& 10&&&&&& 11&&&&&& 23&&&&&& 10&&&&&&& 4
&&&&& 1&&&&&& 23&&&&&&& 3&&&&&& 10&&&&&& 25&&&&&& 31&&&&&& 31&&&&&& 17&&&&&& 28
&&&&& 11&&&&&& 31&&&&&& 27&&&&&& 23&&&&&& 19&&&&&&& 7&&&&&& 19&&&&&& 21&&&&&& 20
&&&&&&& 6&&&&&& 18&&&&&& 14
------------------------------------
27 28 31 31 31
------------------------------------
-----------------------------------
&&& 31&&&&&& 31&&&&&& 31&&&&&& 28&&&&&& 27&&&&&& 26&&&&&& 25&&&&&& 23&&&&&& 23
&&&& 23&&&&&& 21&&&&&& 21&&&&&& 20&&&&&& 19&&&&&& 19&&&&&& 18&&&&&& 17&&&&&& 14
&&&&& 11&&&&&& 11&&&&&& 10&&&&&& 10&&&&&& 10&&&&&&& 7&&&&&&& 7&&&&&&& 6&&&&&&& 4
&&&&&&& 3&&&&&&& 1&&&&&&& 0
Process returned 0 (0x0)&& execution time : 0.030 s
Press any key to continue.
*******************/}