前言

• 生產(chǎn)中的常見(jiàn)問(wèn)題
• 堆的定義
• 堆的基本操作
• 堆排序
• 堆在生產(chǎn)中應(yīng)用

生產(chǎn)中的常見(jiàn)問(wèn)題

1. 優(yōu)先級(jí)隊(duì)列的應(yīng)用場(chǎng)景很廣，它是如何實(shí)現(xiàn)的呢
2. 如何求 Top K 問(wèn)題
3. TP99 是生產(chǎn)中的一個(gè)非常重要的指標(biāo)，如何快速計(jì)算

堆的定義

1. 堆是一顆完全二叉樹(shù)，這樣實(shí)現(xiàn)的堆也被稱為二叉堆
2. 堆中節(jié)點(diǎn)的值都大于等于（或小于等于）其子節(jié)點(diǎn)的值，堆中如果節(jié)點(diǎn)的值都大于等于其子節(jié)點(diǎn)的值，我們把它稱為大頂堆，如果都小于等于其子節(jié)點(diǎn)的值，我們將其稱為小頂堆。

堆的基本操作

• 往堆中插入元素

• 刪除堆頂元素

/**
 * 移除堆頂元素
 */
public void removeTopElement() {
    if (n == 0) {
        // 堆中如果沒(méi)有元素，也就是不存在移除堆頂元素的情況了
        return;
    }
    int count = n;
    arr[1] = arr[count];
    --count;
    heapify(1, count);
}

/**
 * 自上而下堆化以滿足大頂堆的條件
 */
public void heapify(int index, int n) {

    while (true) {
        int maxValueIndex = index;
        if (2 * index <= n && arr[index] < arr[2 * index]) {
            // 左節(jié)點(diǎn)比其父節(jié)點(diǎn)大
            maxValueIndex = 2 * index;
        }

        if (2 * index + 1 <= n && arr[maxValueIndex] < arr[2 * index + 1]) {
            // 右節(jié)點(diǎn)比左節(jié)點(diǎn)或父節(jié)點(diǎn)大
            maxValueIndex = 2 * index + 1;
        }

        if (maxValueIndex == index) {
            // 說(shuō)明當(dāng)前節(jié)點(diǎn)值為最大值，無(wú)需再往下迭代了
            break;
        }
        swap(arr, index, maxValueIndex);
        index = maxValueIndex;
    }
}

/**
 * 交換數(shù)組第 i 和第 j 個(gè)元素
 */
public static void swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

堆排序

用這種方式生成的大頂堆空間復(fù)雜度是多少呢，由于我們新建了一個(gè)數(shù)組，所以空間復(fù)雜度是 O(n)，但其實(shí)堆排序是原地排序的（不需要任何額外空間），所以我們重點(diǎn)看下如何在不需要額外空間的情況下生成大頂堆。

/**
 * 堆排序
 */
public void heapsort() {
    // 建堆
    buildHeap();
    int i = n;
    while (true) {
        if (i <= 1) {
            break;
        }

        // 將堆頂元素放到第 i 個(gè)位置
        swap(arr, 1, i);
        i--;
        // 重新對(duì) 1 到 i 的元素進(jìn)行堆化，以讓其符合大頂堆的條件
        heapify(1, i);
    }
}

堆在生產(chǎn)中應(yīng)用

1. 取 n 個(gè)元素的前 K 個(gè)元素構(gòu)建一個(gè)小頂堆
2. 遍歷第 K + 1 到  n 之間的元素，每一個(gè)元素都與小頂堆的堆頂元素進(jìn)行比較，如果小于堆頂元素，不做任何操作，如果大于堆頂元素，則將堆頂元素替換成當(dāng)前遍歷的元素，再堆化以讓其滿足小頂?shù)囊螅@樣遍歷完成后此小頂堆的所有元素就是我們要求的 TopK。

1. 創(chuàng)建一個(gè)大頂堆和一個(gè)小頂堆，大頂堆的堆頂元素比小頂堆的堆頂元素更小，大頂堆維護(hù) 99% 的請(qǐng)求時(shí)間，小頂堆維護(hù) 1% 的請(qǐng)求時(shí)間
2. 每產(chǎn)生一個(gè)元素（請(qǐng)求時(shí)間），如果它比大頂堆的堆頂元素小，則將其放入到大頂堆中，如果它比小頂堆的堆頂元素大，則將其插入到小頂堆中，插入后當(dāng)然要堆化以讓其符合大小頂堆的要求。
3. 上一步在插入的過(guò)程中需要注意一下，可能會(huì)導(dǎo)致大頂堆和小頂堆中元素的比例不為 99:1，此時(shí)就要做相應(yīng)的調(diào)整，如果在將元素插入大頂堆之后，發(fā)現(xiàn)比例大于 99：1，將需將大頂堆的堆頂元素移到小頂堆中，再對(duì)兩個(gè)堆堆化以讓其符合大小頂堆的要求，同理，如果發(fā)現(xiàn)比例小于 99: 1，則需要將小頂堆的堆頂元素移到大頂堆來(lái)，再對(duì)兩者進(jìn)行堆化。

總結(jié)