堆和堆的应用：堆排序和优先队列
1.堆
堆(heap))是一种重要的数据结构，是实现优先队列(priority queues)首选的数据结构。由于堆有很多种变体，包括二项式堆、斐波那契堆等，但是这里只考虑最常见的就是二叉堆（以下简称堆）。
堆是一棵满足一定性质的二叉树，具体的讲堆具有如下性质：父节点的键值总是不大于它的孩子节点的键值（小顶堆）, 堆可以分为小顶堆和大顶堆，这里以小顶堆为例，其主要包含的操作有：
insert()
extractmin
peek(findmin)
delete(i)
由于堆是一棵形态规则的二叉树，因此堆的父节点和孩子节点存在如下关系：
设父节点的编号为i, 则其左孩子节点的编号为2*i+1, 右孩子节点的编号为2*i+2设孩子节点的编号为i, 则其父节点的编号为(i-1)/2
由于二叉树良好的形态已经包含了父节点和孩子节点的关系信息，因此就可以不使用链表而简单的使用数组来存储堆。
要实现堆的基本操作，涉及到的两个关键的函数
siftup(i, x)： 将位置i的元素x向上调整，以满足堆得性质，常常是用于insert后，用于调整堆；
siftdown(i, x)：同理，常常是用于delete(i)后，用于调整堆；
具体的操作如下：
privatevoidsiftup(inti){
intkey = nums[i];
for(;i > 0;){
intp = (i - 1) >>> 1;
if(nums[p] <= key)
break;
nums[i] = nums[p];
i = p;
}
nums[i] = key;
}
privatevoidsiftdown(inti){
intkey = nums[i];
for(;i < nums.length / 2;){
intchild = (i << 1) + 1;
if(child + 1 nums[child+1])
child++;
if(key = 0;j--)
siftdown(nums,j,size);
}
那么建堆操作的时间复杂度是多少呢？答案是o(n)。虽然siftdown的操作时间是logn，但是由于高度在递减的同时，每一层的节点数量也在成倍减少，最后通过数列错位相减可以得到时间复杂度是o(n)。
extractmin由于堆的固有性质，堆的根便是最小的元素，因此peek操作就是返回根nums[0]元素即可；若要将nums[0]删除，可以将末尾的元素nums[n-1]覆盖nums[0],然后将堆得size = size-1，调用siftdown(0)调整堆。时间复杂度为logn。
peek同上
delete(i)
删除堆中位置为i的节点，涉及到两个函数siftup和siftdown，时间复杂度为logn,具体步骤是，
将元素last覆盖元素i，然后siftdown
检查是否需要siftup
注意到堆的删除操作，如果是删除堆的根节点，则不用考虑执行siftup的操作；若删除的是堆的非根节点，则要视情况决定是siftdown还是siftup操作，两个操作是互斥的。
publicintdelete(inti){
intkey = nums[i];
//将last元素移动过来，先siftdown; 再视情况考虑是否siftup
intlast = nums[i] = nums[size-1];
size--;
siftdown(i);
//check #i的node的键值是否确实发生改变（是否siftdown操作生效）,若发生改变，则ok,否则为确保堆性质，则需要siftup
if(i > 1;j >= 0;j--)
siftdown(j);
}
/**
* append x to heap
* o(logn)
* @param x
* @return
*/
publicintinsert(intx){
if(size >= this.nums.length)
expandspace();
size += 1;
nums[size-1] = x;
siftup(size-1);
returnx;
}
/**
* delete an element located in i position.
* o(logn)
* @param i
* @return
*/
publicintdelete(inti){
rangecheck(i);
intkey = nums[i];
//将last元素覆盖过来,先siftdown; 再视情况考虑是否siftup;
intlast = nums[i] = nums[size-1];
size--;
siftdown(i);
//check #i的node的键值是否确实发生改变,若发生改变，则ok,否则为确保堆性质，则需要siftup;
if(i < size && nums[i] == last)
siftup(i);
returnkey;
}
/**
* remove the root of heap, return it's value, and adjust heap to maintain the heap's property.
* o(logn)
* @return
*/
publicintextractmin(){
rangecheck(0);
intkey = nums[0],last = nums[size-1];
nums[0] = last;
size--;
siftdown(0);
returnkey;
}
/**
* return an element's index, if not exists, return -1;
* o(n)
* @param x
* @return
*/
publicintsearch(intx){
for(inti = 0;i 0;){
intp = (i - 1) >>> 1;
if(nums[p] <= key)
break;
nums[i] = nums[p];
i = p;
}
nums[i] = key;
}
privatevoidsiftdown(inti){
intkey = nums[i];
for(;i < size / 2;){
intchild = (i << 1) + 1;
if(child + 1 nums[child+1])
child++;
if(key <= nums[child])
break;
nums[i] = nums[child];
i = child;
}
nums[i] = key;
}
privatevoidrangecheck(inti){
if(!(0 <= i && i < size))
thrownewruntimeexception(index is out of boundary);
}
privatevoidexpandspace(){
this.nums = arrays.copyof(this.nums,size *2);
}
@override
publicstringtostring(){
// todo auto-generated method stub
stringbuilder sb = newstringbuilder();
sb.append([);
for(inti = 0;i < size;i++)
sb.append(string.format((i != 0?, : ) + %d,nums[i]));
sb.append(] );
returnsb.tostring();
}
}
2.堆的应用：堆排序
运用堆的性质，我们可以得到一种常用的、稳定的、高效的排序算法————堆排序。堆排序的时间复杂度为o(n*log(n))，空间复杂度为o(1)，堆排序的思想是：对于含有n个元素的无序数组nums, 构建一个堆(这里是小顶堆)heap，然后执行extractmin得到最小的元素，这样执行n次得到序列就是排序好的序列。如果是降序排列则是小顶堆；否则利用大顶堆。
trick
由于extractmin执行完毕后，最后一个元素last已经被移动到了root，因此可以将extractmin返回的元素放置于最后，这样可以得到sort in place的堆排序算法。
具体操作如下：
int[]n = newint[]{1,9,5,6,8,3,1,2,5,9,86};
heaph = newheap(n);
for(inti = 0;i = 0;j--)
siftdown(nums,j,size);
}
privatevoidsiftdown(int[]nums,inti,intnewsize){
intkey = nums[i];
while(i >> 1){
intleftchild = (i <= newsize || nums[leftchild] < nums[rightchild])?leftchild : rightchild;
if(key o2.item.freq?1 : o1.item.freq == o2.item.freq?0 : -1;
};
});
nodee = null;
for(inti = 0;i < chs.length;i++){
n[i] = e = newnode(null,null,newitem(chs[i],freq[i]));
pq.add(e);
}
for(inti = 0;i < n.length - 1;i++){
nodex = pq.poll(),y = pq.poll();
nodez = newnode(x,y,newitem('$',x.item.freq + y.item.freq));
pq.add(z);
}
returnpq.poll();
}
/**
* tranversal
* @param root
* @param collector
* @param sb
*/
publicvoidtranversalprefixencodetree(node root,map collector,stringbuilder sb){
// leaf node
if(root.left == null && root.right == null){
collector.put(root.item.c,sb.tostring());
return;
}
node left = root.left,right = root.right;
tranversalprefixencodetree(left,collector,sb.append(0));
sb.delete(sb.length() - 1,sb.length());
tranversalprefixencodetree(right,collector,sb.append(1));
sb.delete(sb.length() - 1,sb.length());
}
}
classnode{
publicnode left,right;
publicitem item;
publicnode(node left,node right,item item){
super();
this.left = left;
this.right = right;
this.item = item;
}
}
classitem{
publiccharc;
publicfloatfreq;
publicitem(charc,floatfreq){
super();
this.c = c;
this.freq = freq;
}
}
输出如下：
{a=0,b=101,c=100,d=111,e=1101,f=1100}
010110001011001101110011011100110111001101010110011110111011011100101110110111001010101100
4 堆的应用：海量实数中（一亿级别以上）找到topk（一万级别以下）的数集合。
a:通常遇到找一个集合中的topk问题，想到的便是排序，因为常见的排序算法例如快排算是比较快了，然后再取出k个topk数，时间复杂度为o(nlogn)，当n很大的时候这个时间复杂度还是很大的；
b:另一种思路就是打擂台的方式,每个元素与k个待选元素比较一次，时间复杂度很高：o(k*n)，此方案明显逊色于前者。
对于一亿数据来说，a方案大约是26.575424*n；
c:由于我们只需要topk，因此不需要对所有数据进行排序，可以利用堆得思想，维护一个大小为k的小顶堆，然后依次遍历每个元素e, 若元素e大于堆顶元素root，则删除root，将e放在堆顶，然后调整，时间复杂度为logk；若小于或等于，则考察下一个元素。这样遍历一遍后，最小堆里面保留的数就是我们要找的topk，整体时间复杂度为o(k+n*logk)约等于o(n*logk)，大约是13.287712*n（由于k与n数量级差太多），这样时间复杂度下降了约一半。
a、b、c三个方案中，c通常是优于b的，因为logk通常是小于k的，当k和n的数量级相差越大，这种方式越有效。
以下为具体操作：
import java.io.file;
import java.io.filenotfoundexception;
import java.io.printwriter;
import java.io.unsupportedencodingexception;
import java.util.arrays;
import java.util.scanner;
import java.util.set;
import java.util.treeset;
publicclasstopknumbersinmassivenumbersdemo{
publicstaticvoidmain(string[]args){
// todo auto-generated method stub
int[]topk = newint[]{50001,50002,50003,50004,50005};
gendata(1000 * 1000 * 1000,500,topk);
longt = system.currenttimemillis();
findtopk(topk.length);
system.out.println(string.format(cost:%fs,(system.currenttimemillis() - t) * 1.0 / 1000));
}
publicstaticvoidgendata(intn,intmaxrandomnumer,int[]topk){
filef = newfile(data.txt);
intk = topk.length;
set index = newtreeset();
for(;;){
index.add((int)(math.random() * n));
if(index.size() == k)
break;
}
system.out.println(index);
intj = 0;
try{
printwriter pw = newprintwriter(f,utf-8);
for(inti = 0;i < n;i++)
if(!index.contains(i))
pw.println((int)(math.random() * maxrandomnumer));
else
pw.println(topk[j++]);
pw.flush();
}catch(filenotfoundexceptione){
// todo auto-generated catch block
e.printstacktrace();
}catch(unsupportedencodingexceptione){
// todo auto-generated catch block
e.printstacktrace();
}
}
publicstaticvoidfindtopk(intk){
int[]nums = newint[k];
//read
filef = newfile(data.txt);
try{
scanner scanner = newscanner(f);
for(intj = 0;j < k;j++)
nums[j] = scanner.nextint();
heapify(nums);
//core
while(scanner.hasnextint()){
inta = scanner.nextint();
if(a > 1;j >= 0;j--)
siftdown(j,size,nums);
}
privatestaticvoidsiftdown(inti,intn,int[]nums){
intkey = nums[i];
for(;i >> 1);){
intchild = (i << 1) + 1;
if(child + 1 nums[child+1])
child++;
if(key <= nums[child])
break;
nums[i] = nums[child];
i = child;
}
nums[i] = key;
}
}
ps:大致测试了一下，10亿个数中找到top5需要140秒左右，应该是很快了。
5 总结
堆是基于树的满足一定约束的重要数据结构，存在许多变体例如二叉堆、二项式堆、斐波那契堆（很高效）等。
堆的几个基本操作都依赖于两个重要的函数siftup和siftdown，堆的insert通常是在堆尾插入新元素并siftup调整堆，而extractmin是在删除堆顶元素，然后将最后一个元素放置堆顶并调用siftdown调整堆。
二叉堆是常用的一种堆，其是一棵二叉树；由于二叉树良好的性质，因此常常采用数组来存储堆。堆得基本操作的时间复杂度如下表所示：
heapify insert peek extractmin delete(i)
o(n) o(logn) o(1) o(logn) o(logn)
二叉堆通常被用来实现堆排序算法，堆排序可以sort in place，堆排序的时间复杂度的上界是o(nlogn)，是一种很优秀的排序算法。由于存在相同键值的两个元素处于两棵子树中，而两个元素的顺序可能会在后续的堆调整中发生改变，因此堆排序不是稳定的。降序排序需要建立小顶堆，升序排序需要建立大顶堆。
堆是实现抽象数据类型优先队列的一种方式，优先队列有很广泛的应用，例如huffman编码中使用优先队列利用贪心算法构建最优前缀编码树。
堆的另一个应用就是在海量数据中找到topk个数，思想是维护一个大小为k的二叉堆，然后不断地比较堆顶元素，判断是否需要执行替换对顶元素的操作，采用此方法的时间复杂度为n*logk，当k和n的数量级差距很大的时候，这种方式是很有效的方法。
6 references
[1]https://en.wikipedia.org/wiki/heap_(data_structure))
[2]https://en.wikipedia.org/wiki/heapsort
[3]https://en.wikipedia.org/wiki/priority_queue
[4]https://www.cnblogs.com/swiftma/p/6006395.html
[5] thomas h.cormen, charles e.leiserson, ronald l.rivest, clifford stein.算法导论[m].北京:机械工业出版社,2015:245-249
[6] jon bentley.编程珠玑[m].北京:人民邮电出版社,2015:161-174
●本文编号591，以后想阅读这篇文章直接输入591即可
●输入m获取文章目录
美光在华遭禁售，对全球存储价格影响巨大
什么是cdma技术
无铅焊接在操作过程中的常见问题
产业集中度将进一步提升，国企龙头的战略定位与调整
LED发光二极管封装过程中的安全防护
堆和堆的应用：堆排序和优先队列
小米Note2怎么样？小米Note2评测：小米Note2升级版本两天后推出，大屏幕长续航或搭载小米MIUI9系统
电流传感器的接线方式
新型激光印刷聚合物电路技术可令电子设备制造成本更低
AMD二代霄龙迎来历史上的最佳机遇
微软Projcet xCloud正式登陆iOS 手机用户可随时随地玩3A大作
苹果公布M1版Mac Mini的功耗数据
基于STM32单片机的简易电子琴设计(2)
全屋智能代表品牌Aqara举办发布会
联亚光电与手持设备制造商合作，利用自有VCSEL开发3D传感解决方案
Redmi路由器AX5采用高通方案，无线速率提升可达52％
友尚推出基于ST 交流半有源整流控制搭配MasterGaN 的200W高功率密度游戏适配器设计方案
红米note5什么时候上市?红米note5曝光:骁龙6305.5英寸,携手小米6plus,本月底发布?
如何实现电源输出电压的动态调整？
DME应答接收机系统设计
堆(heap))是一种重要的数据结构，是实现优先队列(priority queues)首选的数据结构。由于堆有很多种变体，包括二项式堆、斐波那契堆等，但是这里只考虑最常见的就是二叉堆（以下简称堆）。
堆是一棵满足一定性质的二叉树，具体的讲堆具有如下性质：父节点的键值总是不大于它的孩子节点的键值（小顶堆）, 堆可以分为小顶堆和大顶堆，这里以小顶堆为例，其主要包含的操作有：
insert()
extractmin
peek(findmin)
delete(i)
由于堆是一棵形态规则的二叉树，因此堆的父节点和孩子节点存在如下关系：
设父节点的编号为i, 则其左孩子节点的编号为2*i+1, 右孩子节点的编号为2*i+2设孩子节点的编号为i, 则其父节点的编号为(i-1)/2
由于二叉树良好的形态已经包含了父节点和孩子节点的关系信息，因此就可以不使用链表而简单的使用数组来存储堆。
要实现堆的基本操作，涉及到的两个关键的函数
siftup(i, x)： 将位置i的元素x向上调整，以满足堆得性质，常常是用于insert后，用于调整堆；
siftdown(i, x)：同理，常常是用于delete(i)后，用于调整堆；
具体的操作如下：
privatevoidsiftup(inti){
intkey = nums[i];
for(;i > 0;){
intp = (i - 1) >>> 1;
if(nums[p] <= key)
break;
nums[i] = nums[p];
i = p;
}
nums[i] = key;
}
privatevoidsiftdown(inti){
intkey = nums[i];
for(;i < nums.length / 2;){
intchild = (i << 1) + 1;
if(child + 1 nums[child+1])
child++;
if(key = 0;j--)
siftdown(nums,j,size);
}
那么建堆操作的时间复杂度是多少呢？答案是o(n)。虽然siftdown的操作时间是logn，但是由于高度在递减的同时，每一层的节点数量也在成倍减少，最后通过数列错位相减可以得到时间复杂度是o(n)。
extractmin由于堆的固有性质，堆的根便是最小的元素，因此peek操作就是返回根nums[0]元素即可；若要将nums[0]删除，可以将末尾的元素nums[n-1]覆盖nums[0],然后将堆得size = size-1，调用siftdown(0)调整堆。时间复杂度为logn。
peek同上
delete(i)
删除堆中位置为i的节点，涉及到两个函数siftup和siftdown，时间复杂度为logn,具体步骤是，
将元素last覆盖元素i，然后siftdown
检查是否需要siftup
注意到堆的删除操作，如果是删除堆的根节点，则不用考虑执行siftup的操作；若删除的是堆的非根节点，则要视情况决定是siftdown还是siftup操作，两个操作是互斥的。
publicintdelete(inti){
intkey = nums[i];
//将last元素移动过来，先siftdown; 再视情况考虑是否siftup
intlast = nums[i] = nums[size-1];
size--;
siftdown(i);
//check #i的node的键值是否确实发生改变（是否siftdown操作生效）,若发生改变，则ok,否则为确保堆性质，则需要siftup
if(i > 1;j >= 0;j--)
siftdown(j);
}
/**
* append x to heap
* o(logn)
* @param x
* @return
*/
publicintinsert(intx){
if(size >= this.nums.length)
expandspace();
size += 1;
nums[size-1] = x;
siftup(size-1);
returnx;
}
/**
* delete an element located in i position.
* o(logn)
* @param i
* @return
*/
publicintdelete(inti){
rangecheck(i);
intkey = nums[i];
//将last元素覆盖过来,先siftdown; 再视情况考虑是否siftup;
intlast = nums[i] = nums[size-1];
size--;
siftdown(i);
//check #i的node的键值是否确实发生改变,若发生改变，则ok,否则为确保堆性质，则需要siftup;
if(i < size && nums[i] == last)
siftup(i);
returnkey;
}
/**
* remove the root of heap, return it's value, and adjust heap to maintain the heap's property.
* o(logn)
* @return
*/
publicintextractmin(){
rangecheck(0);
intkey = nums[0],last = nums[size-1];
nums[0] = last;
size--;
siftdown(0);
returnkey;
}
/**
* return an element's index, if not exists, return -1;
* o(n)
* @param x
* @return
*/
publicintsearch(intx){
for(inti = 0;i 0;){
intp = (i - 1) >>> 1;
if(nums[p] <= key)
break;
nums[i] = nums[p];
i = p;
}
nums[i] = key;
}
privatevoidsiftdown(inti){
intkey = nums[i];
for(;i < size / 2;){
intchild = (i << 1) + 1;
if(child + 1 nums[child+1])
child++;
if(key <= nums[child])
break;
nums[i] = nums[child];
i = child;
}
nums[i] = key;
}
privatevoidrangecheck(inti){
if(!(0 <= i && i < size))
thrownewruntimeexception(index is out of boundary);
}
privatevoidexpandspace(){
this.nums = arrays.copyof(this.nums,size *2);
}
@override
publicstringtostring(){
// todo auto-generated method stub
stringbuilder sb = newstringbuilder();
sb.append([);
for(inti = 0;i < size;i++)
sb.append(string.format((i != 0?, : ) + %d,nums[i]));
sb.append(] );
returnsb.tostring();
}
}
2.堆的应用：堆排序
运用堆的性质，我们可以得到一种常用的、稳定的、高效的排序算法————堆排序。堆排序的时间复杂度为o(n*log(n))，空间复杂度为o(1)，堆排序的思想是：对于含有n个元素的无序数组nums, 构建一个堆(这里是小顶堆)heap，然后执行extractmin得到最小的元素，这样执行n次得到序列就是排序好的序列。如果是降序排列则是小顶堆；否则利用大顶堆。
trick
由于extractmin执行完毕后，最后一个元素last已经被移动到了root，因此可以将extractmin返回的元素放置于最后，这样可以得到sort in place的堆排序算法。
具体操作如下：
int[]n = newint[]{1,9,5,6,8,3,1,2,5,9,86};
heaph = newheap(n);
for(inti = 0;i = 0;j--)
siftdown(nums,j,size);
}
privatevoidsiftdown(int[]nums,inti,intnewsize){
intkey = nums[i];
while(i >> 1){
intleftchild = (i <= newsize || nums[leftchild] < nums[rightchild])?leftchild : rightchild;
if(key o2.item.freq?1 : o1.item.freq == o2.item.freq?0 : -1;
};
});
nodee = null;
for(inti = 0;i < chs.length;i++){
n[i] = e = newnode(null,null,newitem(chs[i],freq[i]));
pq.add(e);
}
for(inti = 0;i < n.length - 1;i++){
nodex = pq.poll(),y = pq.poll();
nodez = newnode(x,y,newitem('$',x.item.freq + y.item.freq));
pq.add(z);
}
returnpq.poll();
}
/**
* tranversal
* @param root
* @param collector
* @param sb
*/
publicvoidtranversalprefixencodetree(node root,map collector,stringbuilder sb){
// leaf node
if(root.left == null && root.right == null){
collector.put(root.item.c,sb.tostring());
return;
}
node left = root.left,right = root.right;
tranversalprefixencodetree(left,collector,sb.append(0));
sb.delete(sb.length() - 1,sb.length());
tranversalprefixencodetree(right,collector,sb.append(1));
sb.delete(sb.length() - 1,sb.length());
}
}
classnode{
publicnode left,right;
publicitem item;
publicnode(node left,node right,item item){
super();
this.left = left;
this.right = right;
this.item = item;
}
}
classitem{
publiccharc;
publicfloatfreq;
publicitem(charc,floatfreq){
super();
this.c = c;
this.freq = freq;
}
}
输出如下：
{a=0,b=101,c=100,d=111,e=1101,f=1100}
010110001011001101110011011100110111001101010110011110111011011100101110110111001010101100
4 堆的应用：海量实数中（一亿级别以上）找到topk（一万级别以下）的数集合。
a:通常遇到找一个集合中的topk问题，想到的便是排序，因为常见的排序算法例如快排算是比较快了，然后再取出k个topk数，时间复杂度为o(nlogn)，当n很大的时候这个时间复杂度还是很大的；
b:另一种思路就是打擂台的方式,每个元素与k个待选元素比较一次，时间复杂度很高：o(k*n)，此方案明显逊色于前者。
对于一亿数据来说，a方案大约是26.575424*n；
c:由于我们只需要topk，因此不需要对所有数据进行排序，可以利用堆得思想，维护一个大小为k的小顶堆，然后依次遍历每个元素e, 若元素e大于堆顶元素root，则删除root，将e放在堆顶，然后调整，时间复杂度为logk；若小于或等于，则考察下一个元素。这样遍历一遍后，最小堆里面保留的数就是我们要找的topk，整体时间复杂度为o(k+n*logk)约等于o(n*logk)，大约是13.287712*n（由于k与n数量级差太多），这样时间复杂度下降了约一半。
a、b、c三个方案中，c通常是优于b的，因为logk通常是小于k的，当k和n的数量级相差越大，这种方式越有效。
以下为具体操作：
import java.io.file;
import java.io.filenotfoundexception;
import java.io.printwriter;
import java.io.unsupportedencodingexception;
import java.util.arrays;
import java.util.scanner;
import java.util.set;
import java.util.treeset;
publicclasstopknumbersinmassivenumbersdemo{
publicstaticvoidmain(string[]args){
// todo auto-generated method stub
int[]topk = newint[]{50001,50002,50003,50004,50005};
gendata(1000 * 1000 * 1000,500,topk);
longt = system.currenttimemillis();
findtopk(topk.length);
system.out.println(string.format(cost:%fs,(system.currenttimemillis() - t) * 1.0 / 1000));
}
publicstaticvoidgendata(intn,intmaxrandomnumer,int[]topk){
filef = newfile(data.txt);
intk = topk.length;
set index = newtreeset();
for(;;){
index.add((int)(math.random() * n));
if(index.size() == k)
break;
}
system.out.println(index);
intj = 0;
try{
printwriter pw = newprintwriter(f,utf-8);
for(inti = 0;i < n;i++)
if(!index.contains(i))
pw.println((int)(math.random() * maxrandomnumer));
else
pw.println(topk[j++]);
pw.flush();
}catch(filenotfoundexceptione){
// todo auto-generated catch block
e.printstacktrace();
}catch(unsupportedencodingexceptione){
// todo auto-generated catch block
e.printstacktrace();
}
}
publicstaticvoidfindtopk(intk){
int[]nums = newint[k];
//read
filef = newfile(data.txt);
try{
scanner scanner = newscanner(f);
for(intj = 0;j < k;j++)
nums[j] = scanner.nextint();
heapify(nums);
//core
while(scanner.hasnextint()){
inta = scanner.nextint();
if(a > 1;j >= 0;j--)
siftdown(j,size,nums);
}
privatestaticvoidsiftdown(inti,intn,int[]nums){
intkey = nums[i];
for(;i >> 1);){
intchild = (i << 1) + 1;
if(child + 1 nums[child+1])
child++;
if(key <= nums[child])
break;
nums[i] = nums[child];
i = child;
}
nums[i] = key;
}
}
ps:大致测试了一下，10亿个数中找到top5需要140秒左右，应该是很快了。
5 总结
堆是基于树的满足一定约束的重要数据结构，存在许多变体例如二叉堆、二项式堆、斐波那契堆（很高效）等。
堆的几个基本操作都依赖于两个重要的函数siftup和siftdown，堆的insert通常是在堆尾插入新元素并siftup调整堆，而extractmin是在删除堆顶元素，然后将最后一个元素放置堆顶并调用siftdown调整堆。
二叉堆是常用的一种堆，其是一棵二叉树；由于二叉树良好的性质，因此常常采用数组来存储堆。堆得基本操作的时间复杂度如下表所示：
heapify insert peek extractmin delete(i)
o(n) o(logn) o(1) o(logn) o(logn)
二叉堆通常被用来实现堆排序算法，堆排序可以sort in place，堆排序的时间复杂度的上界是o(nlogn)，是一种很优秀的排序算法。由于存在相同键值的两个元素处于两棵子树中，而两个元素的顺序可能会在后续的堆调整中发生改变，因此堆排序不是稳定的。降序排序需要建立小顶堆，升序排序需要建立大顶堆。
堆是实现抽象数据类型优先队列的一种方式，优先队列有很广泛的应用，例如huffman编码中使用优先队列利用贪心算法构建最优前缀编码树。
堆的另一个应用就是在海量数据中找到topk个数，思想是维护一个大小为k的二叉堆，然后不断地比较堆顶元素，判断是否需要执行替换对顶元素的操作，采用此方法的时间复杂度为n*logk，当k和n的数量级差距很大的时候，这种方式是很有效的方法。
6 references
[1]https://en.wikipedia.org/wiki/heap_(data_structure))
[2]https://en.wikipedia.org/wiki/heapsort
[3]https://en.wikipedia.org/wiki/priority_queue
[4]https://www.cnblogs.com/swiftma/p/6006395.html
[5] thomas h.cormen, charles e.leiserson, ronald l.rivest, clifford stein.算法导论[m].北京:机械工业出版社,2015:245-249
[6] jon bentley.编程珠玑[m].北京:人民邮电出版社,2015:161-174
●本文编号591，以后想阅读这篇文章直接输入591即可
●输入m获取文章目录
美光在华遭禁售，对全球存储价格影响巨大
什么是cdma技术
无铅焊接在操作过程中的常见问题
产业集中度将进一步提升，国企龙头的战略定位与调整
LED发光二极管封装过程中的安全防护
堆和堆的应用：堆排序和优先队列
小米Note2怎么样？小米Note2评测：小米Note2升级版本两天后推出，大屏幕长续航或搭载小米MIUI9系统
电流传感器的接线方式
新型激光印刷聚合物电路技术可令电子设备制造成本更低
AMD二代霄龙迎来历史上的最佳机遇
微软Projcet xCloud正式登陆iOS 手机用户可随时随地玩3A大作
苹果公布M1版Mac Mini的功耗数据
基于STM32单片机的简易电子琴设计(2)
全屋智能代表品牌Aqara举办发布会
联亚光电与手持设备制造商合作，利用自有VCSEL开发3D传感解决方案
Redmi路由器AX5采用高通方案，无线速率提升可达52％
友尚推出基于ST 交流半有源整流控制搭配MasterGaN 的200W高功率密度游戏适配器设计方案
红米note5什么时候上市?红米note5曝光:骁龙6305.5英寸,携手小米6plus,本月底发布?
如何实现电源输出电压的动态调整？
DME应答接收机系统设计