本文共 3800 字，大约阅读时间需要 12 分钟。
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 res = findLeastK(array, 3); System.out.println(res.toString()); ArrayList res2 = findLeastK_priorityQueue(array, 3); System.out.println(res2.toString()); } //思路1：堆排序 public static ArrayList findLeastK(int [] array,int k) { ArrayList res = new ArrayList (); 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 findLeastK_priorityQueue(int[] input, int k) { ArrayList result = new ArrayList (); int length = input.length; if(k > length || k == 0){ return result; } //priorityQueue默认为小根堆 PriorityQueue maxHeap = new PriorityQueue (k, new Comparator () { 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; }} 在此记录一下。
另附我的另一篇关于排序总结的博客， 链接：转载地址：http://jvdgi.baihongyu.com/