關於堆的一切

来源:https://www.cnblogs.com/Sugar-Cube/p/18040667
-Advertisement-
Play Games

前置知識 首先給出堆的定義: 堆是一顆樹,滿足堆的性質,即: 對於一個節點,它的權值大於(或小於)它的各個兒子的權值 有這個性質,顯然 堆的根節點權值是整個堆中最大或最小的 由此可分為小根堆和大根堆 二叉堆 最常見的堆就是二叉堆 二叉堆是一顆滿足堆的性質的完全二叉樹 顯然,二叉堆的子樹也是二叉堆 接 ...


前置知識

首先給出堆的定義:
堆是一顆樹,滿足堆的性質,即:
對於一個節點,它的權值大於(或小於)它的各個兒子的權值

有這個性質,顯然
堆的根節點權值是整個堆中最大或最小的
由此可分為小根堆大根堆

二叉堆

最常見的堆就是二叉堆
二叉堆是一顆滿足堆的性質完全二叉樹
顯然,二叉堆的子樹也是二叉堆

接下來,我們以小根堆為例:

當一個節點權值小於其父親時,我們嘗試不斷將這個節點與父親交換,直到其滿足堆的性質
這就是向上調整

同理,
當一個節點權值大於其父親時,我們嘗試不斷將這個節點與其兩個兒子中權值較小的一個交換,直到其滿足堆的性質
這就是向下調整

為什麼這裡要與權值較小的一個交換呢?
因為我們要使交換後滿足堆的性質
所以新的父節點權值應小於它的兩個兒子

由於堆的高度為 \(\log{n}\)
所以以上兩個操作複雜度顯然為 \(\mathcal {O}(\log{n})\)

那麼有了這兩個操作我們就可以完成:
插入(新建節點然後向上調整)
查詢最大(最小)值(根節點權值)
刪除最大(最小)值(與末尾節點交換,再向下調整)
刪除任意節點(與末尾交換,再向上或向下調整,見代碼)
修改任意節點權值(向上或向下調整)

Luogu (模板)堆

#include<bits/stdc++.h>

using namespace std;

static constexpr int AwA = 1e6 + 10;

inline static int Read() {
    int res = 0;
    bool flag = false;
    int c = getchar();
    while ((c < '0' || c > '9') && ~c) {
        flag |= c == '-';
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        res = (res << 1) + (res << 3) + (c ^ 48);
        c = getchar();
    }
    return flag ? -res : res;
}

//這裡我們認為一個節點的父親是u<<1,左兒子為u>>1,右兒子為u>>1|1
//根為1
//由堆為完全二叉樹的性質可得只需開一倍數組
int val[AwA];
//儲存總節點數
int len;

inline void MoveUp(int u) {
    while (u >> 1) {
        int fa = u >> 1;
        if (val[fa] <= val[u]) break;
        swap(val[fa], val[u]);
        u = fa;
    }
}

inline void MoveDown(int u) {
    while (u << 1 <= len) {
        int son = u << 1;
        if (son < len && val[son | 1] < val[son]) son |= 1;
        if (val[u] <= val[son]) break;
        swap(val[u], val[son]);
        u = son;
    }
}

inline int GetTop() { return val[1]; }

inline void Pop() {
    swap(val[1], val[len]);
    len--;
    MoveDown(1);
}

inline void Push(int _val) {
    val[++len] = _val;
    MoveUp(len);
}

//刪除任意已知節點
inline void Delete(int u) {
    swap(val[u], val[len]);
    len--;
    if (val[u << 1] <= val[u]) MoveDown(u);
    else MoveUp(u);
}

//每次對於根進行向下調整,來合併左右兒子代表的兩個堆
//OIwiki上有證明,這種建樹是O(n)的
inline void Build(int _len, const int *a) {
    len = _len;
    memcpy(val + 1, a + 1, sizeof(int) * len);
    //葉子節點不調整,減小常數
    for (int i = (len >> 1) - 1; i; i--) MoveDown(i);
}

int main() {
    int n = Read();
    while (n--) {
        int op = Read();
        if (op == 1) Push(Read());
        else if (op == 2) printf("%d\n", GetTop());
        else Pop();
    }
    return 0;
}

此外,對於這段代碼,我們來仔細討論一下:

inline void Build(int _len, const int *a) {
    len = _len;
    memcpy(val + 1, a + 1, sizeof(int) * len);
    for (int i = (len >> 1) - 1; i; i--) MoveDown(i);
}

這段代碼可以在 \(\mathcal {O}(n)\) 時間內建堆
我們按照節點bfs序倒序向下調整
每當調整到一個節點時
該節點的左右兒子所在子樹已然是二叉堆
這時再把根節點向下調整滿足堆的性質
可視為左右兒子代表的二叉堆的合併

證明:
待補充

可並堆

待補充

其他堆

待補充


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

-Advertisement-
Play Games
更多相關文章
  • Java 包和 API Java 中的包 用於將相關的類分組在一起。可以將其視為文件目錄中的一個文件夾。我們使用包來避免名稱衝突,並編寫更易於維護的代碼。 包分為兩類: 內置包(來自 Java API 的包) 用戶定義的包(創建自己的包) 內置包 Java API 是一個預先編寫的類庫,可以在 Ja ...
  • Rust的智能指針有哪些?大多數人都能馬上答出Box<T>、Rc<T>和Arc<T>、Ref<T>和在非同步編程中很常見的Pin<P>等等。不過,有一個可能經常被大多數人遺忘的類型,它功能強大,利用好了可以節省很多複製開銷;它就是這篇文章的主角:Cow<B>。 什麼是COW(Copy-On-Write ...
  • 1.pom.xml引入依賴 <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper</artifactId> <version>5.1.11</version> </dependency> 2.myba ...
  • 1.問題: 有如下代碼: public class Test { static { i = 0;// 給變數賦值可以正常編譯通過 System.out.print(i);// 編譯器會提示“非法向前引用”(illegal forward reference) } static int i = 1; ...
  • 線程安全 線程安全是多線程或多進程編程中的一個概念,在擁有共用數據的多條線程並行執行的程式中,線程安全的代碼會通過同步機制保證各個線程都可以正常且正確的執行,不會出現數據污染等意外情況。 線程安全的問題最主要還是由線程切換導致的,比如一個房間(進程)中有10顆糖(資源),除此之外還有3個小人(1個主 ...
  • 1.標準庫參考:shutil.rmtree。 根據設計,rmtree在包含只讀文件的文件夾樹上失敗。如果要刪除文件夾,不管它是否包含只讀文件,請使用 import shutil shutil.rmtree('/folder_name', ignore_errors=True) 2.從os.walk( ...
  • 在原文上有刪減,原文鏈接Rust 的面向對象特性。 目錄面向對象語言的特征對象包含數據和行為封裝隱藏了實現細節繼承,作為類型系統與代碼共用顧及不同類型值的 trait 對象定義通用行為的 trait實現 traittrait 對象執行動態分發麵向對象設計模式的實現定義 Post 並新建一個草案狀態的 ...
  • 一、測試運行python項目 1.1 Flask項目 說明1:當我們直接用編譯器運行Flask項目的時候,會有一個提示:意思就是:這是開發環境的伺服器,不能用於生產環境的部署,請使用WSGI的伺服器替換 1.2 Django項目 說明2:當我們直接用編譯器運行Django項目的時候,同樣有個提示,這 ...
一周排行
    -Advertisement-
    Play Games
  • 不廢話,直接代碼 private Stack<Action> actionStack = new Stack<Action>(); private void SetCellValues() { var worksheet = Globals.ThisAddIn.Application.ActiveS ...
  • OpenAPI 規範是用於描述 HTTP API 的標準。該標準允許開發人員定義 API 的形狀,這些 API 可以插入到客戶端生成器、伺服器生成器、測試工具、文檔等中。儘管該標準具有普遍性和普遍性,但 ASP.NET Core 在框架內預設不提供對 OpenAPI 的支持。 當前 ASP.NET ...
  • @DateTimeFormat 和 @JsonFormat 是 Spring 和 Jackson 中用於處理日期時間格式的註解,它們有不同的作用: @DateTimeFormat @DateTimeFormat 是 Spring 框架提供的註解,用於指定字元串如何轉換為日期時間類型,以及如何格式化日 ...
  • 一、背景說明 1.1 效果演示 用python開發的爬蟲採集軟體,可自動抓取抖音評論數據,並且含二級評論! 為什麼有了源碼還開發界面軟體呢?方便不懂編程代碼的小白用戶使用,無需安裝python、無需懂代碼,雙擊打開即用! 軟體界面截圖: 爬取結果截圖: 以上。 1.2 演示視頻 軟體運行演示視頻:見 ...
  • SpringBoot筆記 SpringBoot文檔 官網: https://spring.io/projects/spring-boot 學習文檔: https://docs.spring.io/spring-boot/docs/current/reference/html/ 線上API: http ...
  • 作為後端工程師,多數情況都是給別人提供介面,寫的好不好使你得重視起來。 最近我手頭一些活,需要和外部公司對接,我們需要提供一個介面文檔,這樣可以節省雙方時間、也可以防止後續扯皮。這是就要考驗我的介面是否規範化。 1. 介面名稱清晰、明確 顧名思義,介面是做什麼的,是否準確、清晰?讓使用這一眼就能知道 ...
  • 本文介紹基於Python語言,遍歷文件夾並從中找到文件名稱符合我們需求的多個.txt格式文本文件,並從上述每一個文本文件中,找到我們需要的指定數據,最後得到所有文本文件中我們需要的數據的合集的方法~ ...
  • Java JUC&多線程 基礎完整版 目錄Java JUC&多線程 基礎完整版1、 多線程的第一種啟動方式之繼承Thread類2、多線程的第二種啟動方式之實現Runnable介面3、多線程的第三種實現方式之實現Callable介面4、多線的常用成員方法5、線程的優先順序6、守護線程7、線程的讓出8、線 ...
  • 實時識別關鍵詞是一種能夠將搜索結果提升至新的高度的API介面。它可以幫助我們更有效地分析文本,並提取出關鍵詞,以便進行進一步的處理和分析。 該介面是挖數據平臺提供的,有三種模式:精確模式、全模式和搜索引擎模式。不同的模式在分詞的方式上有所不同,適用於不同的場景。 首先是精確模式。這種模式會儘量將句子 ...
  • 1 為啥要折騰搭建一個專屬圖床? 技術大佬寫博客都用 md 格式,要在多平臺發佈,圖片就得有外鏈 後續如博客遷移,國內博客網站如掘金,簡書,語雀等都做了防盜鏈,圖片無法遷移 2 為啥選擇CloudFlare R2 跳轉:https://dash.cloudflare.com/ 有白嫖額度 免費 CD ...