top k算法讲解

在实际工作中，我们时常会有寻找长度为n的数组中，排在前k的元素，对于top k的问题，最暴力的处理方式就是直接对数组进行排序，然后再去截取前k个数字，从而达到自己的目的，这种算法的实现复杂度为O（nlogn），其实有O（n）的算法或者是O（nlogk）时间复杂度的算法。

• 基于快排的top k算法

  如果我们了解快速排序算法的话，知道其原理是每次寻找一个数值，将数组中所有小于这个数的值放在其左侧，所有大于其数值的数放在其右侧。因此调用一次partion之后，设其返回值为p，则比第p个数字小的所有数字在数组的左侧，比第p个数字大的所有数字都在数组的右侧。我们可以基于快排的原理用其实现寻找top k的元素。我们看下代码，其时间复杂度为O（n）。

    private static int partion(int[] array, int low, int high) {

        int mid = array[low];
        while (low < high) {
            while (low < high && array[high] >= mid)
                high--;
            array[low] = array[high];
            while (low < high && array[low] <= mid)
                low++;
            array[high] = array[low];
        }
        array[low] = mid;
        return low;
    }

    private static int top_k(int[] array, int k) {

        if (array == null || array.length == 0)
            return -1;
        if (k < 0 || k > array.length - 1)
            return -1;
        int low = 0, high = array.length - 1;
        int index = partion(array, low, high);
        while (index != k) {
            if (index > k) {
                high = index - 1;
                index = partion(array, low, high);

            } else {
                low = index + 1;
                index = partion(array, low, high);
            }
        }
        return array[index];
    }

• 基于大顶堆的top k算法
  这种算法适合海量数据的情况下，比如我们待查找的数据很大，甚至不可以一次全部读入内存，这种方法就比较适合。下面简单说一下其原理。
  我们先创建一个大小为k的数组来存储最小的k个数字，接下来我们从输入的n个数中读取一个数，如果容器还没有满则直接插入容器；若容器已经满了，则我们此时需要将容器中最大的数字和待插入的数字做比较，如果待插入的数值小于容器中的最大值，则需要将容器中的最大值删除，将新值插入，否则不做任何处理。
  我们通过需求分析可以发现，大顶堆可以满足我们的需求，因此我们通过大顶堆来实现我们的容器，其代码如下，时间复杂度为O（nlogk）。

    private final int MAXSIZE = 10 + 1;
    private int currentSize = 1;

    private void heap_insert(int[] array, int value) {

        if (currentSize < MAXSIZE) {
            array[currentSize++] = value;
            if (currentSize == MAXSIZE) {
                for (int i = currentSize / 2; i > 0; i--) {
                    heap_adjust(array, i, currentSize);
                }
            }
        } else {
            int max = array[1];
            if (value < max) {
                array[1] = value;
                heap_adjust(array, 1, currentSize);
            }
        }
    }

    // 堆调整
    private void heap_adjust(int[] array, int s, int len) {
        int temp = array[s];
        for (int i = 2 * s; i < len; i *= 2) {
            if (i < len - 1 && array[i] < array[i + 1])
                i++;
            if (array[i] <= temp)
                break;
            array[s] = array[i];
            s = i;
        }
        array[s] = temp;

    }

我们可以注意到数组的第0个元素并没有使用，因为大顶堆是基于完全二叉树的原理实现，因此角标0不可以存储元素，具体说明可见排序算法文章中的堆排序部分：http://blog.csdn.net/dingpiao190/article/details/72674199

另外补充一点，这个大顶堆的数据结构是我们自己来维护的，对于Java而言，其实可以直接借助于JDK中的TreeSet集合来实现，因为TreeSet是有序的集合，其基于红黑树来实现。同理，对于C++来讲，可以借助set集合实现。Java基于TreeSet实现的代码如下：

private static TreeSet<Integer> topk(int[] array, int n) {

        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int i = 0; i < array.length; i++) {

            int value = array[i];
            if (set.size() < n)
                set.add(value);
            else {
                Iterator<Integer> it = set.descendingIterator();
                int setMax = it.next();
                if (setMax > value ) {
                    it.remove();
                    set.add(value);
                }
            }
        }
        return set;

    }

，