二叉堆的應用

有一個無序數組,要求你找出數組中第k大的元素。

給定的無序數組如下：

7	5	15	3	17	2	20	24	1	9	12	8

如果 k=6，也就是要尋找第6大的元素，這個元素是哪一個呢？

顯然，數組中第一大的元素是24，第二大的元素是20，第三大的元素是17 … 第6大的元素是9。

7	5	15	3	17	2	20	24	1	9	12	8
4	3	2	1	6	5

經典的做法：利用小頂堆的特性。

維護一個容量為k的小頂堆，堆中的k個節點代表着目前最大的k個元素，而堆頂顯然是這k個元素中的最小值。

周遊原數組，每周遊一個元素，就和堆頂比較，如果目前元素小于等于堆頂，則繼續周遊；如果元素大于堆頂，則把目前元素放在堆頂位置，并調整二叉堆（下沉操作）。

周遊結束後，堆頂就是數組的最大k個元素中的最小值，也就是第k大元素。

假設k=5，具體的執行步驟如下：

1.把數組的前k個元素建構成堆。

2.繼續周遊數組，和堆頂比較，如果小于等于堆頂，則繼續周遊；如果大于堆頂，則取代堆頂元素并調整堆。

周遊到元素2，由于 2<3，是以繼續周遊。

周遊到元素20，由于 20>3，20取代堆頂位置，并調整堆。

以此類推，我們一個一個周遊元素，當周遊到最後一個元素8的時候，小頂堆的情況如下：

此時的堆頂，就是堆中的最小值，也就是數組中的第k大元素

這個方法的時間複雜度是多少呢？

1.建構堆的時間複雜度是 O（k）

2.周遊剩餘數組的時間複雜度是O（n-k）

3.每次調整堆的時間複雜度是 O（logk）

其中2和3是嵌套關系，1和2,3是并列關系，是以總的最壞時間複雜度是 O ( ( n − k ) l o g k + k ) O((n-k)logk + k) O((n−k)logk+k)。當k遠小于n的情況下，也可以近似地認為是 O ( n l o g k ) O(nlogk) O(nlogk),方法的空間複雜度是 O ( 1 ) O(1) O(1)。

public class Solution{
    /**
     * 尋找第k大的元素
     * @param array 待調整的堆
     * @param k 第幾大
     */
    public static int findNumberK(int[] array, int k){
        //1.用前k個元素建構小頂堆
        buildHeap(array, k);
        //2.繼續周遊數組，和堆頂比較
        for(int i=k; i<array.length;i++){
            if(array[i] > array[0]){
                array[0] = array[i];
                downAdjust(array, 0, k);
            }
        }
        //3.傳回堆頂元素
        return array[0];
    }

    /**
     * 建構堆
     * @param array 待調整的堆
     * @param length 堆的有效大小
     */
    private static void buildHeap(int[] array, int length) {
        // 從最後一個非葉子節點開始，依次下沉調整
        for (int i = (length-2)/2; i >= 0; i--) {
            downAdjust(array, i, length);
        }
    }

    /**
     * 下沉調整
     * @param array   待調整的堆
     * @param index  要下沉的節點
     * @param length  堆的有效大小
     */
    private static void downAdjust(int[] array, int index, int length) {
        // temp儲存父節點值，用于最後的指派
        int temp = array[index];
        int childIndex = 2 * index + 1;
        while (childIndex < length) {
            // 如果有右孩子，且右孩子小于左孩子的值，則定位到右孩子
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }
            // 如果父節點小于任何一個孩子的值，直接跳出
            if (temp <= array[childIndex])
                break;
            //無需真正交換，單向指派即可
            array[index] = array[childIndex];
            index = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[index] = temp;
    }
    public static void main(String[] args) {
        int[] array = new int[] {7,5,15,3,17,2,20,24,1,9,12,8};
        System.out.println(findNumberK(array,5));
    }
}
           

此題還有一個分治法

大家都了解快速排序，快速排序利用分治法，每一次把數組分成較大和較小的兩部分。

我們在尋找第k大元素的時候，也可以利用這個思路，以某個元素A為基準，把大于于A的元素都交換到數組左邊，小于A的元素都交換到數組右邊。

比如我們選擇以元素7作為基準，把數組分成了左側較大，右側較小的兩個區域，交換結果如下：

包括元素7在内的較大元素有8個，但我們的k=5，顯然較大元素的數目過多了。于是我們在較大元素的區域繼續分治，這次以元素12位基準：

這樣一來，包括元素12在内的較大元素有5個，正好和k相等。是以，基準元素12就是我們所求的。

這就是分治法的大體思想，這種方法的時間複雜度甚至優于小頂堆法，可以達到 O ( n ) O(n) O(n)。

來源于「程式員小灰」公衆号的文章，

版權聲明：本文為CSDN部落客「qq_36264495」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。

原文連結：https://blog.csdn.net/qq_36264495/article/details/85611470