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 == )
            return -;
        if (k <  || k > array.length - )
            return -;
        int low = , high = array.length - ;
        int index = partion(array, low, high);
        while (index != k) {
            if (index > k) {
                high = index - ;
                index = partion(array, low, high);

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

• 基于大頂堆的top k算法

  這種算法适合海量資料的情況下，比如我們待查找的資料很大，甚至不可以一次全部讀入記憶體，這種方法就比較适合。下面簡單說一下其原理。

  我們先建立一個大小為k的數組來存儲最小的k個數字，接下來我們從輸入的n個數中讀取一個數，如果容器還沒有滿則直接插入容器；若容器已經滿了，則我們此時需要将容器中最大的數字和待插入的數字做比較，如果待插入的數值小于容器中的最大值，則需要将容器中的最大值删除，将新值插入，否則不做任何處理。

  我們通過需求分析可以發現，大頂堆可以滿足我們的需求，是以我們通過大頂堆來實作我們的容器，其代碼如下，時間複雜度為O（nlogk）。

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

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

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

    // 堆調整
    private void heap_adjust(int[] array, int s, int len) {
        int temp = array[s];
        for (int i =  * s; i < len; i *= ) {
            if (i < len -  && array[i] < array[i + ])
                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 = ; 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;

    }
           

，