大根堆和小根堆的介紹

来源:https://www.cnblogs.com/Tomorrowland/p/18343313
-Advertisement-
Play Games

堆(Heap)的基本概念 堆是一種完全二叉樹(Complete Binary Tree),其性質使得堆可以高效地支持以下操作: 插入(Insert):將一個新元素加入到堆中。 刪除最大/最小元素(Delete Max/Min):移除並返回堆中的最大(大根堆)或最小(小根堆)元素。 獲取最大/最小元素 ...


堆(Heap)的基本概念

堆是一種完全二叉樹(Complete Binary Tree),其性質使得堆可以高效地支持以下操作:

  • 插入(Insert):將一個新元素加入到堆中。
  • 刪除最大/最小元素(Delete Max/Min):移除並返回堆中的最大(大根堆)或最小(小根堆)元素。
  • 獲取最大/最小元素(Get Max/Min):返回堆中的最大(大根堆)或最小(小根堆)元素。

大根堆(Max-Heap)

特性

  • 每個節點的值都大於或等於其子節點的值。
  • 根節點是堆中最大的元素。

插入操作

  1. 將新元素插入到樹的最底層的最後位置(保持完全二叉樹的性質)。
  2. 進行“上浮”操作,將新元素逐步與其父節點交換,直到堆的性質恢復或到達根節點為止。

刪除最大元素

  1. 移除根節點。
  2. 將最後一個元素移動到根位置。
  3. 進行“下沉”操作,將根節點逐步與其較大的子節點交換,直到堆的性質恢復或到達葉子節點為止。

小根堆(Min-Heap)

特性

  • 每個節點的值都小於或等於其子節點的值。
  • 根節點是堆中最小的元素。

插入操作

  1. 將新元素插入到樹的最底層的最後位置(保持完全二叉樹的性質)。
  2. 進行“上浮”操作,將新元素逐步與其父節點交換,直到堆的性質恢復或到達根節點為止。

刪除最小元素

  1. 移除根節點。
  2. 將最後一個元素移動到根位置。
  3. 進行“下沉”操作,將根節點逐步與其較小的子節點交換,直到堆的性質恢復或到達葉子節點為止。

C++ 示例代碼

以下是詳細的 C++ 示例代碼,展示如何實現大根堆和小根堆:

#include <iostream>
//在c++中,使用優先隊列需要包含queue這個頭文件
#include <queue>
#include <vector>

// 大根堆(預設行為)
void maxHeapExample() {
    // 創建一個大根堆
    std::priority_queue<int> maxHeap;

    // 插入元素
    maxHeap.push(10);
    maxHeap.push(20);
    maxHeap.push(5);
    maxHeap.push(15);

    std::cout << "Max-Heap (大根堆): ";
    // 輸出並刪除堆頂元素
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " "; // 獲取堆頂元素
        maxHeap.pop(); // 刪除堆頂元素
    }
    std::cout << std::endl;
}

// 小根堆
void minHeapExample() {
    // 自定義比較函數,逆序(大根堆),實現小根堆
    auto cmp = [](int left, int right) { return left > right; };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> minHeap(cmp);

    // 插入元素
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);
    minHeap.push(15);

    std::cout << "Min-Heap (小根堆): ";
    // 輸出並刪除堆頂元素
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " "; // 獲取堆頂元素
        minHeap.pop(); // 刪除堆頂元素
    }
    std::cout << std::endl;
}

int main() {
    maxHeapExample();
    minHeapExample();

    return 0;
}

代碼解釋

  1. 大根堆(Max-Heap)
    • std::priority_queue<int> 預設是大根堆。priority_queue 是 STL 提供的容器適配器,基於堆實現。
    • 插入元素使用 push(),獲取堆頂元素使用 top(),刪除堆頂元素使用 pop()
  2. 小根堆(Min-Heap)
    • 通過自定義比較函數來實現小根堆。std::priority_queue 的構造函數允許傳遞自定義的比較函數。
    • auto cmp = [](int left, int right) { return left > right; }; 是一個 lambda 表達式,用於將小根堆的比較函數定義為 left > right
    • 構造 priority_queue 時,傳遞 cmp 作為比較函數,這樣就會形成小根堆。

小根堆的實現細節與第二種實現方式

在 C++ 的 priority_queue 中,如果你不顯式地提供第二個模板參數(即底層容器類型),它會預設使用 std::vector 作為底層容器。這意味著,你可以只指定元素類型和比較函數(或者不指定比較函數,使用預設的比較方式),而不必顯式地指定底層容器類型。

示例:

#include <iostream>
#include <queue>

struct Compare {
    bool operator()(int left, int right) {
        // 小根堆的比較規則:左邊的值小於右邊的值返回 true
        return left > right;
    }
};

void minHeapExample() {
    // 不顯式指定底層容器類型,仍然會使用預設的 std::vector<int>
    std::priority_queue<int, std::vector<int>, Compare> minHeap;

    // 插入元素
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);
    minHeap.push(15);

    std::cout << "Min-Heap (小根堆): ";

    // 輸出並刪除堆頂元素
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " "; // 獲取堆頂元素
        minHeap.pop(); // 刪除堆頂元素
    }
    std::cout << std::endl;
}

int main() {
    minHeapExample();

    return 0;
}

解釋:

  • std::priority_queue<int, std::vector<int>, Compare> minHeap; 中,我們沒有顯式地提供第二個模板參數(底層容器類型),因此預設使用 std::vector<int>
  • 這樣做的好處是簡化了代碼,使其更具可讀性,並且仍然能夠正常使用小根堆的功能。
  • 如果你想要使用除了 std::vector 以外的其他底層容器,你可以顯式地指定第二個模板參數,例如 std::deque<int> 或者其他適合的容器類型。

因此,答案是:可以不顯式提供第二個模板參數 std::vector<int>priority_queue 能夠識別到並使用預設的 std::vector 作為底層容器類型。

比較規則的解釋

在 C++ 的 priority_queue 中,如果我們想要實現一個小根堆(Min Heap),是使用 left > right 的比較規則。

比較規則解釋:

  1. 小根堆(Min Heap)

    • 在小根堆中,父節點的值應該小於或等於每個子節點的值。
    • 因此,在 C++ 的 priority_queue 中,應該使用比較函數或者仿函數,確保 leftright 大,即 left > right
  2. 大根堆(Max Heap)

    • 在大根堆中,父節點的值應該大於或等於每個子節點的值。
    • 因此,比較函數應該返回 left < right

示例解釋:

如果要實現一個小根堆,確保堆頂元素是最小的,比較函數應該是這樣定義的:

struct MinHeapComparator {
    bool operator()(int left, int right) {
        return left > right;
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, MinHeapComparator> minHeap;

    minHeap.push(10);
    minHeap.push(2);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(13);

    while (!minHeap.empty()) {
        int t = minHeap.top();
        minHeap.pop();
        std::cout << t << " ";
    }

    return 0;
}

在這個示例中,MinHeapComparator 是一個仿函數,它實現了小根堆的比較規則 left > right,確保了堆頂的元素是最小的。

總結:

對於小根堆的實現,確實應該使用 left > right 的比較規則。這個比較規則確保了在堆中,父節點的值小於或等於每個子節點的值,從而滿足小根堆的特性。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 題目要求 給你一個由 n 個整數組成的數組 nums ,和一個目標值 target 。請你找出並返回滿足下述全部條件且不重覆的四元組 [nums[a], nums[b], nums[c], nums[d]] (若兩個四元組元素一一對應,則認為兩個四元組重覆): 0 <= a, b, c, d < n ...
  • 2018年6月,大三暑假 那一天,我投遞了家裡附近的一家公司有響應了,他線上問我什麼時候可以去面試,我說什麼時候都行。 HR:“要不你下午來吧?” 我:“行,我家裡離面試地點不遠” 我去面試之前,現在都會提前看看這家公司是做什麼業務的,先瞭解下。 因為在之前的面試已經吃過類似的虧了,HR問我為什麼要 ...
  • PART 1: while迴圈 雙重for迴圈 1. 迴圈結構(while迴圈語句) 基本格式 while(判斷條件語句) { 迴圈體語句; } 擴展格式 初始化語句; while(判斷條件語句) { 迴圈體語句; 控制條件語句; } 2. 迴圈結構(for迴圈和while迴圈的區別) for迴圈和 ...
  • 寫在前面 前面給了關於java方法和數組的十題編程題,如果你能有思路很快速地完成它,說明你這部分的基礎知識很好,接下來就來看看後面的面向對象的相關知識吧! 面向對象 概述:不斷地創建對象,使用對象,指揮對象做事情的思想。 類和對象的關係: 類: 是java的基本單位,主要使用用於描述現實生活的事物。 ...
  • # 字元串長度 - strlen() 描述 C 庫函數 size_t strlen(const char *str) 計算字元串 str 的長度,直到空結束字元,但不包括空結束字元。 聲明 下麵是 strlen() 函數的聲明。 size_t strlen(const char *str) 參數 s ...
  • P1223 排隊接水 題目描述 有 \(n\) 個人在一個水龍頭前排隊接水,假如每個人接水的時間為 \(T_i\),請編程找出這 \(n\) 個人排隊的一種順序,使得 \(n\) 個人的平均等待時間最小。 輸入格式 第一行為一個整數 \(n\)。 第二行 \(n\) 個整數,第 \(i\) 個整數 ...
  • 將Word文檔以圖片形式導出,既能方便信息的分享,也能保護數據安全,避免被二次編輯。文本將介紹如何使用 Spire.Doc for Python 庫在Python程式中實現Word到圖片的批量轉換。 Python 將Word轉換為JPG、JPEG、PNG、BMP等圖片格式 Python 將Word文 ...
  • 安裝Nginx並配置訪問 安裝PHP並輸出腳本結果 配置typecho Nginx安裝並驗證 apt install nginx systemctl start nginx 正常情況應該可以看到Nginx的歡迎頁面了,如果看不到就是防火牆的問題,設置下防火牆放通即可。 安裝PHP並使用Nginx代理 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...