问题描述

问题描述：有 N （N>1000000）个数，求出其中的前 k 个最大的数（又被称为 topK 问题）
解决思路：

  • 直接思路：将这 N 个数进行完全排序，再进行切片即可，复杂度跟所使用的排序算法有关，一般快排、堆排序和归并排序都能达到 O(n*logn) 的复杂度
  • 使用优先队列，选择其中前 k 个数做为数据池，后面的 N-k 个数与这 k 个数进行比较，如果其大于其中任一一个数，则进行替换，算法复杂度为O(n*k)
  • 使用冒泡排序：由于冒泡排序属于一次次将当前最大的值移至后面，因此只需要进行 k 次遍历即可，O(n*k)
  • 使用小根堆：先对前 k 个元素建立小根堆，然后再对后面的 N - k 个元素与小根堆的堆顶进行比较，如果该值大与小根堆的堆顶，则替换堆顶，再进行一次堆的向下调整，该算法时间复杂度为 O(n*logk)
    • 该算法优点：不需要一次性将数据全部加载进内存
  • 快速排序：利用快速排序的分划函数找到分划位置k，则前面内容即为所求，时间复杂度O(n)

小根堆实现—java版本

  1. 小根堆的头结点的元素值为整个小根堆的最小值，只要当前值大于小根堆的头结点，即可以进行覆盖

  2. 没进行一次覆盖，均需要进行一次小根堆的向下调整，所以时间复杂度为O(n*logk)，k 为需要获取的长度

    1. public class HeapDemo {
    2.  public static void main(String[] args) {
    3.      // 生成一个超大的数组
    4.      int[] arr = new int[10000];
    5.      // 生成初始化参数
    6.      Random random = new Random();
    8.      for (int i = 0; i < 10000; i++) {
    9.          arr[i] = random.nextInt(10000);
    10.      }
    12.      // 选取前100大的元素
    13.      // 新建结果数组
    14.      int[] res = new int[100];
    15.      // 将原数组中的前100个元素拷贝进结果数组
    16.      System.arraycopy(arr, 0, res, 0, 100);
    18.      // 创建小根堆
    19.      build(res, res.length);
    21.      // 将数组中的后10000-100个元素与小堆顶进行比较，如果大于小根堆的头结点，则将该值赋给小根堆的头结点进行覆盖
    22.      for (int i = 100; i < 10000; i++) {
    23.          if (arr[i] > res[0]) {
    24.              res[0] = arr[i];
    25.              heapify(res, 0, res.length);
    26.          }
    27.      }
    28.      System.out.println(Arrays.toString(res));
    29.  }
    31.  /**
    32.   * 创建小根堆
    33.   *
    34.   * @param arr 数组
    35.   * @param len 数组中有效元素的个数
    36.   */
    37.  public static void build(int[] arr, int len) {
    38.      // 最后一个非叶子结点的索引
    39.      int index = (len - 2) >> 1;
    41.      // 从最后一个非叶子结点开始调整堆
    42.      while (index >= 0) {
    43.          // 调整非叶子结点建立小堆
    44.          heapify(arr, index--, len);
    45.      }
    46.  }
    48.  /**
    49.   * 堆的向下调整
    50.   *
    51.   * @param arr  数组
    52.   * @param root 根结点的索引
    53.   * @param len  数组中有效元素数量
    54.   */
    55.  private static void heapify(int[] arr, int root, int len) {
    56.      // 左子结点的位置
    57.      int left = (root << 1) + 1;
    58.      // 根结点、左右字节中最小值的元素索引
    59.      int min = root;
    61.      // 循环调整
    62.      while (left < len) {
    63.          // 左子结点比根结点小
    64.          if (arr[left] < arr[min]) {
    65.              min = left;
    66.          }
    67.          // 右子节点存在且比左子结点和根结点都小
    68.          if (left + 1 < len && arr[left + 1] < arr[min]) {
    69.              min = left + 1;
    70.          }
    71.          if (min != root) {
    72.              // 需要进行结点交换和下一次的循环
    73.              swap(arr, min, root);
    74.              // 调整root结点的位置
    75.              root = min;
    76.              left = (root << 1) + 1;
    77.          } else {
    78.              // 说明根结点最小，已经满足小根堆
    79.              break;
    80.          }
    81.      }
    82.  }
    84.  // 交换数组中两个元素的值
    85.  private static void swap(int[] arr, int x, int y) {
    86.      arr[x] ^= arr[y];
    87.      arr[y] ^= arr[x];
    88.      arr[x] ^= arr[y];
    89.  }
    90. }

快速排序实现