1.堆的基本概念
堆实际上是一颗完全二叉树，其中，任何一个非叶子节点均满足如下性质：
key[i]<=key[2*i+1]&&key[i]<=key[2*i+2] （小顶堆） 或
key[i]>=key[2*i+1]&&key[i]>=key[2*i+2] （大顶堆）
其中i是从0开始的。
2.堆排序的思想
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
其基本思想为(大顶堆)：
1)将初始待排序关键字序列(R0,R1....Rn-1)构建成大顶堆，此堆为初始的无序区；
2)将堆顶元素R[0]与最后一个元素R[n-1]交换，此时得到新的无序区(R0,R1,......Rn-2)和新的有序区(Rn-1),且满足R[0,1...n-2]<=R[n-1];
3)由于交换后新的堆顶R[0]可能违反堆的性质，因此需要对当前无序区(R0,R1,......Rn-2)调整为新堆，然后再次将R[0]与无序区最后一个元素交换，得到新的无序区(R0,R1....Rn-3)和新的有序区(Rn-2,Rn-1)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
注意：上述算法描述与《算法导论》上有一点点的差别，算法导论上将元素的第一个值标记为R1，因此每个元素的下标相差1.为了有利于程序实现，以上均是按照数组从0开始的习惯进行描述的
Java代码实现：
/*
* $filename: HeapSort.java,v $
* $Date: 2014-3-17 $
* Copyright (C) ZhengHaibo, Inc. All rights reserved.
* This software is Made by Zhenghaibo.
*/
package edu.njupt.zhb;
/*
*@author: ZhengHaibo
*web: http://blog.csdn.net/nuptboyzhb
*mail: zhb931706659@126.com
*2014-3-9 Nanjing,njupt,China
*/
public class HeapSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int []a = {12,5,6,98,45,2,4,9};
myHeapSort(a);
for(int e:a){
System.out.println(e);
}
}
/**
* 最大堆调整
* 将data当中范围为[i~high]的元素调整为
* 以i为根的子树调整为最大堆
* @param data
* @param i
* @param high
*/
public static void maxHeapify(int []data,int i,int high){
int left=2*i+1;//左子树
int right=2*i+2;//右子树
int largest=i;//定义一个最大值
if(left<=high&&data[left]>data[i]){
largest=left;
}
if(right<=high&&data[right]>data[largest]){
largest=right;
}
if(largest!=i){//如果最大值不是根节点，将根节点和最大值交换
int temp=data[i];
data[i]=data[largest];
data[largest]=temp;
//由于交换，可能其子树不满足最大堆，继续向后调整，使其子树成为最大堆
maxHeapify(data,largest,high);
}
}
/**
* 堆排序
* 1.建立堆
* 2.逐步输出堆中的最大值
* @param data
*/
public static void myHeapSort(int []data){
int n=data.length;
//建立堆，由于n/2及以后的元素肯定是叶子节点，可看为大小为1的最大堆
//因此从最后一个叶子节点逐步向前调整
//调整结果：data[0]为根节点的最大堆
for(int i=n/2-1;i>=0;i--){
maxHeapify(data,i,n-1);
}
//此时，data是一个data[0]为根节点的最大堆
//逐步将data[0]与最后一个元素交换，然后再将0~n-2调整为最大堆
//相当于逐步将堆的最大元素放到数组最后的过程
for(int i=n-1;i>=1;i--){
int temp=data[0];
data[0]=data[i];
data[i]=temp;
maxHeapify(data,0,i-1);
}
}
}
3.优先队列
优先队列和队列很像，只是优先队列的出列是按照优先级大小出列的。优先队列可以用对来实现。
package edu.njupt.zhb;
/*
*@author: ZhengHaibo
*web: http://blog.csdn.net/nuptboyzhb
*mail: zhb931706659@126.com
*2014-3-15 Nanjing,njupt,China
*/
/**
*使用二叉堆实现优先队列
*说明：
*为了演示优先队列的功能，该优先队列只支持整型的数据
*/
public class MyPriorityQueue {
final int INIT_LEN=10;
int size;
int datas[];
public MyPriorityQueue(){
datas=new int[INIT_LEN];
size=0;
}
public boolean isEmpty(){
return size<=0;
}
/**
* 获取堆顶的元素
* 最大值
* @return
*/
public int peek(){
if(datas.length<1){
System.out.println("ERROR");
return -1;
}
return datas[0];
}
/**
* 入列
* 向堆中添加一个元素，添加后的仍为一个堆
* @param data
*/
public void add(int data){
if(size>=datas.length){//扩充数组
int []temp=new int[datas.length+INIT_LEN];
for(int i=0;i<datas.length-1;i++){
temp[i]=datas[i];
}
datas=temp;
}
datas[size++]=data;//将数据添加到末尾
for(int i=size/2;i>=0;i--){//建立堆
maxHeapify(datas, i, size-1);
}
}
/**
* 出列
* 取出堆中最大的元素,并删除之
* @return
*/
public int remove(){
int data=datas[0];//将堆顶数据取出
for(int i=1;i<size;i++){//平移
datas[i-1]=datas[i];
}
size--;
for(int i=size/2-1;i>=0;i--){//将新的数组建立堆
maxHeapify(datas, i, size);
}
return data;
}
/**
* 最大堆调整
* 将data当中范围为[i~high]的元素调整为
* 以i为根的子树调整为最大堆
* @param data
* @param i
* @param high
*/
public void maxHeapify(int []data,int i,int high){
int left=2*i+1;//左子树
int right=2*i+2;//右子树
int largest=i;//定义一个最大值
if(left<=high&&data[left]>data[i]){
largest=left;
}
if(right<=high&&data[right]>data[largest]){
largest=right;
}
if(largest!=i){//如果最大值不是根节点，将根节点和最大值交换
int temp=data[i];
data[i]=data[largest];
data[largest]=temp;
maxHeapify(data,largest,high);//继续调节最大值的子树，使其成为最大堆
}
}
public static void main(String[] args) {
MyPriorityQueue queue=new MyPriorityQueue();
int []datas={2,54,23,56,8,65,3};
for(int data:datas){
queue.add(data);
}
while(!queue.isEmpty()){
System.out.println(queue.remove());
}
}
}
3.堆排序的应用：TopK
1.首先，我们看一下这个问题：输出一个数组中第二大的值
我们分析的思路是：初始化一个最大值和第二大的值，然后逐步扫描。
1）如果当前值a[i]>maxV，则将secV=maxV;maxV=a[i];
2) 如果当前值a[i]>secV或者secV==maxV&&a[i]<maxV，则secV=a[i]
代码如下：
/**
* 查找第二大的值
* 时间复杂度O(n)
* 空间复杂度O(1)
* @param data
*/
public static void findSecondMax(int []data){
int maxValue=data[0];
int secValue=data[0];
for(int i=1;i<data.length;i++){
if(data[i]>maxValue){
secValue=maxValue;
maxValue=data[i];
}else if(data[i]>secValue||(secValue==maxValue&&data[i]<secValue)){
secValue=data[i];
}
}
if(maxValue>secValue){
System.out.println(secValue);
return;
}
System.out.println("不存在第二大的值");
}
2.如果要查找很大的一组数（n很大）中的前K个最大值（k<<n），我们应该怎么办呢？显然，上面的思路，我们代码写起来就会比较麻烦，而且效率还不高。我们可以根据堆排序的特点，借助堆排序。
1）首先建立堆，时间复杂度为O(n)
2）只需要输出前K个最大值即可，也就是调整k次即可
空间复杂度O(1)
代码如下：
/**
* 查找data中的最大的前K个值
* @param data
* @param k
*/
public static void findTopK(int []data,int k){
if(k>=data.length){
return;
}
int n=data.length;
for(int i=n/2-1;i>=0;i--){//建堆的时间复杂度为O(n)
maxHeapify(data,i,n-1);
}
for(int i=n-1;i>=n-k;i--){//只需要调整k次即可
System.out.println(data[0]);
int temp=data[0];
data[0]=data[i];
data[i]=temp;
maxHeapify(data,0,i-1);
}
}
/**
* 堆调整
* @param data
* @param low
* @param high
*/
private static void maxHeapify(int[] data, int low, int high) {
// TODO Auto-generated method stub
int left=2*low+1;
int right=2*low+2;
int largest=low;
if(left<=high&&data[left]>data[largest]){
largest=left;
}
if(right<=high&&data[right]>data[largest]){
largest=right;
}
if(largest!=low){
int temp=data[low];
data[low]=data[largest];
data[largest]=temp;
maxHeapify(data, largest, high);
}
}
3.当data数据数据量有1T时。且存储在硬盘上，显然无法一次性读入到内存中进行排序，此时，求解这些数据的TopK。
我们的思路是：初始化一个大小为K的数组result，然后建立最小堆，使得result[0]最小，然后逐个遍历data中的数据，如果比result[0]大，就将其替换result[0]，然后调整最小堆，依次遍历结束。
/**
* 查找topK
* 思路：result为存放topK的数组，首先将data中的前K个元素复制到result中
* 对result建立最小堆，使result[0]为最小值。
* 其次，遍历data中剩余的元素，如果data[i]大于result[0],那么就用data[i]代替result[0]
* 然后调整堆，使result[0]成为最小值。依次遍历结束
* 优点：当data很大时，无法将data直接读入到内存时，用该方式很合适！
* 时间复杂度：O(K)+O(K)+O(n*logK)
* @param data
* @param result
*/
public static void findTopK(int []data,int []result){
if(result.length>=data.length){
return;
}
for(int i=0;i<result.length;i++){//初始化result O(K)
result[i]=data[i];
}
for(int i=result.length/2-1;i>=0;i--){//对result数组建堆 O(K)
minHeapify(result, i, result.length-1);
}
for(int i=result.length;i<data.length;i++){//O(n*logK)
if(data[i]>result[0]){
result[0]=data[i];
minHeapify(result,0,result.length-1);
}
}
}
/**
* 最小堆调整
* @param data
* @param low
* @param high
*/
private static void minHeapify(int []data,int low,int high){
int left=2*low+1;
int right=2*low+2;
int small=low;
if(left<=high&&data[left]<data[small]){
small=left;
}
if(right<=high&&data[right]<data[small]){
small=right;
}
if(small!=low){
int temp=data[low];
data[low]=data[small];
data[small]=temp;
minHeapify(data, small, high);
}
}
参考博文：
[1]http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html