小頂堆和大頂堆詳解

一、小頂堆和大頂堆stl

STL中提供了小頂堆和大頂堆的實現，可以通過傳入比較函數來指定為小頂堆和大頂堆。例如：

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    // 小頂堆
    priority_queue<int, vector<int>, greater<int>> pq1;
    pq1.push(3);
    pq1.push(1);
    pq1.push(2);
    while (!pq1.empty())
    {
        cout << pq1.top() << " ";
        pq1.pop();
    }
    // 輸出結果為：1 2 3

    // 大頂堆
    priority_queue<int, vector<int>> pq2;
    pq2.push(3);
    pq2.push(1);
    pq2.push(2);
    while (!pq2.empty())
    {
        cout << pq2.top() << " ";
        pq2.pop();
    }
    // 輸出結果為：3 2 1

    return 0;
}

二、小頂堆和大頂堆區別

小頂堆是一種每個節點都小於等於其父節點的完全二叉樹，最小的元素在根節點，而大頂堆是每個節點都大於等於其子節點的完全二叉樹，最大的元素在根節點。在實現中，小頂堆和大頂堆都需要維護堆的性質，即父節點與其子節點之間的大小關係。

三、大頂堆小頂堆的定義

大頂堆是一種每個節點都大於等於其子節點的完全二叉樹，最大的元素在根節點，而小頂堆是每個節點都小於等於其父節點的完全二叉樹，最小的元素在根節點。在實現中，大頂堆和小頂堆都需要維護堆的性質，即父節點與其子節點之間的大小關係。

四、大根堆和大頂堆的區別

大根堆和大頂堆都是指每個節點都大於等於其子節點的完全二叉樹，最大的元素在根節點，但是在實現細節上有所不同。大頂堆採用的是數組實現，而大根堆採用的是二叉搜索樹實現，因此插入和刪除元素時，大根堆要做平衡調整。

五、大頂堆和小根堆的區別

小根堆是一種每個節點都小於等於其子節點的完全二叉樹，最小的元素在根節點，與大頂堆相反。在實現中，小根堆和大頂堆都需要維護堆的性質，即父節點與其子節點之間的大小關係。

六、大根堆和小頂堆圖解

大根堆和小頂堆的結構圖如下：

七、構建大頂堆

大頂堆的構建過程一般採用從最後一個非葉子節點開始進行向下調整的方式，通過不斷比較父節點和其子節點的大小關係進行調整，確保每個節點都大於等於其子節點。例如，以下是構建大頂堆的代碼實現：

void buildMaxHeap(int *arr, int len)
{
    for (int i = len / 2 - 1; i >= 0; i--)
    {
        adjustDown(arr, i, len);
    }
}

八、構造大頂堆

構造大頂堆的過程就是不斷將堆中最大的元素移動到堆頂，保證堆性質不變。具體實現可以通過將堆尾元素和堆頂元素進行交換，然後將堆頂元素向下調整。例如，以下是構造大頂堆的代碼實現：

void heapSort(int *arr, int len)
{
    // 構建大頂堆
    buildMaxHeap(arr, len);

    // 不斷取出堆頂元素放到數組末尾
    for (int i = len - 1; i > 0; i--)
    {
        swap(arr[0], arr[i]);
        adjustDown(arr, 0, i);
    }
}

九、初始堆是大頂堆還是小頂堆

初始堆是指構建堆前的數組，可以是亂序排列的元素。默認情況下，STL中提供的堆函數是大頂堆。如果想要構建小頂堆，需要在函數中傳入比較函數greater。

十、大頂堆建堆過程圖示

以下是從數組構建大頂堆的過程示意圖，可以清晰地看出每一步的調整過程。