關於堆的一切

来源: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
  • C#.Net的BCL提供了豐富的類型,最基礎的是值類型、引用類型,而他們的共同(隱私)祖先是 System.Object(萬物之源),所以任何類型都可以轉換為Object。 ...
  • 最近有群友咨詢C#如何調用Python?小編嘗試Python.NET過程中遭遇的版本相容性和環境配置難題,小編決定尋找一個更為簡單、穩定且對初學者友好的解決方案。小編搜索一番,除了Python.NET之外,還有其他途徑能夠幫助我們輕鬆地在C#項目調用Python腳本,那就是通過命令行調用,使用 Sy ...
  • .NET中特性+反射 實現數據校驗 在.NET中,我們可以使用特性+反射來實現數據校驗。特性是一種用於為程式中的代碼添加元數據的機制。元數據是與程式中的代碼相關聯的數據,但不直接成為代碼的一部分。通過特性,我們可以為類、方法、屬性等添加額外的信息,這些信息可以在運行時通過反射獲取和使用。 對反射不太 ...
  • Biwen.Settings 是一個簡易的配置項管理模塊,主要的作用就是可以校驗並持久化配置項,比如將自己的配置存儲到資料庫中,JSON文件中等 使用上也是很簡單,只需要在服務中註入配置, 比如我們有一個GithubSetting的配置項,我們只需要定義好對象然後註入到Service中即可: [De ...
  • EDP是一套集組織架構,許可權框架【功能許可權,操作許可權,數據訪問許可權,WebApi許可權】,自動化日誌,動態Interface,WebApi管理等基礎功能於一體的,基於.net的企業應用開發框架。通過友好的編碼方式實現數據行、列許可權的管控。 ...
  • 前言 VB.NET,全名Visual Basic .NET,是Microsoft .NET框架的一部分,是一種面向對象的編程語言。它繼承了Visual Basic的易用性,同時增加了對面向對象編程的支持。VB.NET提供了大量的內置函數,使得開發者可以更容易地處理字元串、數學計算、文件和目錄訪問等任 ...
  • 自定義可移動點二維坐標軸控制項 目錄 路由參數 坐標軸控制項定義 Demo 路由參數 X_YResultCollection為當前X軸對應Y軸值存儲字典 public class ResultCollectionChangedEventArgs(RoutedEvent routedEvent, obje ...
  • 自定義分頁控制項 tip: 該控制項的樣式用的是materialDesign庫,需要下載Nuget包 Code Xaml <UserControl x:Class="TestTool.CustomControls.PagingControl" xmlns="http://schemas.microsof ...
  • 最近群里有個小伙伴把Dapper遷移SqlSugar幾個不能解決的問題進行一個彙總,我正好寫一篇文章來講解一下 一、sql where in傳參問題: SELECT * FROM users where id IN @ids 答: SqlSugar中應該是 var sql="SELECT * FRO ...
  • 安裝nuget包 Wesky.Net.OpenTools 1.0.8或以上版本。支持.net framework 4.6以上版本,以及所有.net core以及以上版本引用。 開發一個簡單的Winform界面,用來測試使用。如需該winform的demo,可以在公眾號【Dotnet Dancer】後 ...