面试-堆排序(heapSort)以及最大/小的k个数-java实现

Q：

同学面试腾讯的时候被问到：王者荣耀用户上亿，如何快速的从亿级数据量中找出排名榜首的几位玩家？

A:

对于这种数据量比较大的情况，堆排序比较合适，而且堆排序每一轮可以找出当前数据中最大（大顶堆）或最小（小顶堆）的数，所以对于以上问题，用堆排序是不错的选择。

以找出输入数据中【最小的k个数】为例，java实现如下：

package com.sap.stone;
import java.util.*;

public class FindLeastK{
	public static void main(String[] args) {
		int []array = {1,5,3,9,7,8,6,2,4};
		ArrayList<Integer> res = findLeastK(array, 3);
		System.out.println(res.toString());
		ArrayList<Integer> res2 = findLeastK_priorityQueue(array, 3);
		System.out.println(res2.toString());
	}
	//思路1：堆排序
	public static ArrayList<Integer> findLeastK(int [] array,int k) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		int [] temp = new int[k];
		for (int i = 0; i < k; i++) {
			temp[i] = array[i];
		}
		for (int i = k/2; i >= 0; i--) {
			adjustHeap(temp, i, k - 1);
		}
		for (int j = k; j < array.length; j++) {
			if (temp[0] > array[j]) {  //存在更小的数字
				temp[0] = array[j];
				adjustHeap(temp, 0, k-1); //重新调整堆
			}
		}
		for (int i = 0; i < k; i++) {
			res.add(temp[i]);
		}
		return res;
	}

	private static void adjustHeap(int []array,int start,int end) {
		int temp = array[start];
		int child = start*2 + 1;
		while (child <= end) {
			if (child+1 <= end && array[child + 1] > array[child]) {
				child++;
			}
			if (array[child] < temp) {  //如果所有的孩子节点都小于父节点，就结束循环
				break;
			}else {
				array[start] = array[child];
				start = child; //迭代
				child = child*2 + 1;
			}
		} //end while
		array[start] = temp;
	}
	
	/**
	 * 交换元素
	 */
	public static void swap(int []array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	
	//思路2:使用priorityQueue
	public static ArrayList<Integer> findLeastK_priorityQueue(int[] input, int k) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        int length = input.length;
        if(k > length || k == 0){
            return result;
        }
        //priorityQueue默认为小根堆
	    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
	        public int compare(Integer o1, Integer o2) {
	            return o2.compareTo(o1);    //本例使用大根堆，逆序
	        }
	    });
	    for (int i = 0; i < length; i++) {
	        if (maxHeap.size() != k) {
	            maxHeap.offer(input[i]);
	        } else if (maxHeap.peek() > input[i]) {
	            Integer temp = maxHeap.poll();
	            temp = null;
	            maxHeap.offer(input[i]);
	        }
	    }
	    for (Integer integer : maxHeap) {
	        result.add(integer);
	    }
	    return result;
    }
}
           

堆排序实现如下：

package com.sap.stone;

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * 堆排序：【不稳定】【适合大容量数据】
 * 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
 * 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
 * 思路：
 * 	1.将无序序列构建成堆，升序大顶堆（降序小顶堆）
 * 	2.将堆顶元素与末尾元素进行交换，使数组末尾元素最大。
 * 	3.然后继续调整堆，再将堆顶元素与当前末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
 * @author stone
 * 最好,最坏,平均时间复杂度都是O(nlogn)
 */

public class HeapSort {
	public static void main(String[] args) {
		int []array = {1,5,3,9,7,8,6,2,4};
		heapSort(array);
		System.out.println(Arrays.toString(array));
		System.out.println("\"\"");// ""的转义
	}
	public static void heapSort(int[] array) {
		int length = array.length;
		//build heap
		for (int i = length/2; i >= 0; i--) {
			adjustHeap(array, i, length-1);
		}
		//exchange, adjust heap
		for (int i = array.length - 1; i > 0; i--) {
			swap(array, 0, i);
			adjustHeap(array, 0, i-1);
		}
	}
	//调整堆
	private static void adjustHeap(int []array,int start,int end) {
		int temp = array[start];
		int child = start*2 + 1;
		while (child <= end) {
			if (child+1 <= end && array[child + 1] > array[child]) {
				child++;
			}
			if (array[child] < temp) {  //如果所有的孩子节点都小于父节点，就结束循环
				break;
			}else {
				array[start] = array[child];
				start = child; //迭代
				child = child*2 + 1;
			}
		} //end while
		array[start] = temp;
	}
	
	/**
	 * 交换元素
	 */
	public static void swap(int []array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}

           

在此记录一下。

另附我的另一篇关于排序总结的博客，笔试面试–总结7大常用排序算法（Java实现&详细）

链接：https://blog.csdn.net/u010947534/article/details/96893099