重温数据结构：堆，堆排序，优先队列，TopK问题_python 大顶堆优先队列

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);
		}
	}

查找nums中第K大的数

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int item : nums) {
            if (priorityQueue.size() < k) {
                priorityQueue.offer(item);
            } else {
                Integer min = priorityQueue.peek();
                if (item > min) {
                    priorityQueue.offer(item);
                }
            }
        }
        return priorityQueue.peek();
    }

参考博文：

[1]堆排序 - Matrix海子 - 博客园

[2]数据结构之优先队列--二叉堆(Java实现)_java先进先出数据结构_LCore的博客-CSDN博客

[3]堆排序实现以及相关笔试题_WA说的博客-CSDN博客