Top K问题 ----堆排序_减治法求解堆排序

问题大致描述:

在海量数据中选出前K个最大的数据

输入:

    第一行：输入K，表示要求选出的K个最大的数

    第二行：输入一个数

     ......

    第n-1行:输入一个数

    第n行:输入-1表示结束

(其中K要<=输入的个数)

输出：

  输出前K的最大的数

 

思路：因为要在海量的数据中选出K个数，所以可以利用堆排序，建立小根堆，

在用户输入的数小于k的时候，则不需要选出K个数，直接保存到数组中即可

在用户输入k个数的时候，直接用数组建立一个小根堆，则arr[0]就是其最小的数

若用户输入的数>K的时候，需要用输入的数与arr[0]做比较：

                                           如果输入的数大于arr[0]，则将输入的数赋值给arr[0]，并调整小根堆

                                           如果输入的数小于等于arr[0]，无需操作

 

Java代码:

import java.util.Scanner;
 
/**
	 * 前K个数
	 * TopK
	 *
	 */
public class Main {
	static int[] heap;    //保存前K的数的数组
	static int index = 0;    //标记数组中最后一个元素的位置
	static int k;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		k = in.nextInt();	//输入k
		heap = new int[k];
		int x = in.nextInt();
		while(x!=-1) {
			deal(x);	//处理x
			x = in.nextInt();
		}
		printRs();
	}
	//打印输出K个数
	public static void printRs() {
		for(int i = 0; i < heap.length; i++)
			System.out.print(heap[i] + " ");
	}
	//对x进行处理
	public static void deal(int x) {
		if(index<k) {
			heap[index++] = x;
			//当index==k时需要立即进行堆化
			if(index==k) {
				//堆化
				MakeMinHeap(heap);
				index++;
			}
			return;
		}
		
		//x和堆顶进行比较,若x大于堆顶，x将堆顶挤掉并向下调整
		if(heap[0]<x) {
			heap[0] = x;
			MinHeapFixDown(heap, 0);
		}
	}
	//堆化,一般这个方法只在初始的时候使用一次就行
	public static void MakeMinHeap(int[] arr) {
		int n = arr.length;
		for(int i = n/2-1;i>=0;i--)
			MinHeapFixDown(arr,i);
	}
		
	//调整堆，使堆形成小根堆
	public static void MinHeapFixDown(int[] arr,int i) {
		int n = arr.length;
		//先找到左右孩子
		int left = 2*i+1;
		int right = 2*i+2;
		if(left>=n)	//若左孩子已经越界，i就是叶子节点
			return;
		int min = left;
		if(right>=n)	//若右孩子越界,则左孩子就是最小的
			min = left;
		else if(arr[right]<arr[left])
			min = right;
		//这样min指向左右孩子中较小的那个
		
		//如果arr[i]比两个孩子都要小，不用调整
		if(arr[i]<=arr[min])
			return;
		//否则，找到两个孩子中较小的，和i交换
		int temp = arr[i];
		arr[i] = arr[min];
		arr[min] = temp;
		//小孩子那个位置的值发送了变化，i变更为小孩子那个位置，递归调整
		MinHeapFixDown(arr,min);
	}
}

 

总结：

做这个题，必须熟练掌握堆排序的内容！