基本信息
拼音：duī
堆注音：ㄉㄨㄟˉ
部首：土
五筆輸入法：fwyg
筆畫數：11
筆順編號：12132411121
漢字釋義
基本解釋
1、累積在一起的東西：堆疊。堆房。土堆。2、累積在一起，聚積在一起：堆積。堆放。堆壘。堆摞。堆砌。
3、量詞，用於成堆的物或成群的人：一堆人。
詳細解釋
【名】1、形聲。字從土，從隹（zhuī），隹亦聲。“隹”為“錐”省。“土”與“隹”聯合起來表示“錐形土包”。本義：錐形土包。
2、土堆；土墩，沙墩或水中聚集的礁石。
逾隴堆兮渡漠。——《楚辭·疾世》
激堆埼。——司馬相如《上林賦》
呼水中沙堆為墠。——《爾雅·釋水》注
3、常為排列的整齊有序的疊堆。如：草堆；柴火堆；堆雲（形容密集眾多）；堆堆（久久不動的樣子；形容累積得很多的樣子）。
【動】
堆積。堆，聚土。——《說文》
【量】
用來計量成堆的東西。捲起千堆雪。——宋·蘇軾《念奴嬌·赤壁懷古》
常用詞語
1.堆冰duībīng[packice]由大小浮冰推擠在一起形成混雜體的海上冰塊
2.堆疊duīdié
[pileup]一層一層地碼起來
案上堆疊著一摞新教材
3.堆垛duīduò
[rick]堆積成垛（如乾草）
4.堆房duīfáng
[storeroom;wareroom]堆放雜物或貨物的貯藏室
5.堆放duīfàng
（1）[pileup]∶把貨物放到或扔到堆上
采來的條石堆放在屋檐下
（2）[stack]∶成堆地放置大量的東西，尤其是整整齊齊地存放
把稻草堆放在打穀場上
6.堆肥duīféi
[stockmanure;compost]一種通常是把糞便、雜草、莖葉泥土等堆起來發酵後製成，其大部分是由腐敗的有機物組成的混合物，用作肥料和改良土質
7.堆穀場duīgǔchǎng
[stackyard]堆放禾桿或穀物的場地或田地
8.堆焊duīhàn
[repairwelding]把金屬熔化堆在工具或機器零件上的焊接法。用來修復機件的磨損、崩裂部分（常用電焊或氣焊法）
9.堆積duījī
（1）[heapup]∶把事物堆集成堆糧食堆積如山
（2）[store]∶集中成堆放置
林蔭路中心常用來堆積冬天從路面上掃出來的雪
10.堆集duījí
[heap]成堆地聚在一起；堆積
案頭堆集著畫軸
11.堆集如山duījí-rúshān
（1）[lieinaheap;pileuplikeamountain]東西堆積得像山一樣。形容極多
每遇冬月，諸鄉納粟稈草，牛車闐塞道路，車尾相銜，數千萬輛不絕，場內堆集如山。——宋·孟元老《東京夢華錄·外諸司》
（2）亦作“堆積如山”
12.堆金積玉duījīn-jīyù
[amassafortune]形容財產多，非常富有
13.堆聚duījù
[heapup]堆積；聚集
堆聚成山
14.堆壘duīlěi
[pileup]堆疊
15.堆內duīnèi
[in-pile]表示在反應堆內進行實驗或安放設備的術語
16.堆砌duīqì
[pad;(fig)loadone'swritingwithfancyphrases]壘積磚石並用泥灰黏合，比喻寫文章使用大量華麗而無用的詞語，以擴大或加長篇幅（如書籍、雜誌的文章、講話）
17.堆土duītǔ
[bank]沿[正在成長的莊稼如芹菜的]埂堆土以保護植物或使之不見陽光而變白
18.堆笑duīxiào
[showingallsmiles]顯露笑容
滿臉堆笑
19.堆疊duīzhàn
[storehouse;warehouse;godown]臨時暫存貨物的地方
堆(數據結構)
堆（英語：heap)是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質：堆中某個節點的值總是不大於或不小於其父節點的值；
堆總是一棵完全樹。
將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。
堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}若且唯若滿足下關係時，稱之為堆。
(ki<=k2i,ki<=k2i+1)或者(ki>=k2i,ki>=k2i+1),(i=1,2,3,4...n/2)
若將和此次序列對應的一維數組（即以一維數組作此序列的存儲結構）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大於（或不小於）其左、右孩子結點的值。由此，若序列{k1,k2,…,kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。
支持的基本操作
堆支持以下的基本:build:建立一個空堆；
insert:向堆中插入一個新元素；
update：將新元素提升使其符合堆的性質；
get：獲取當前堆頂元素的值；
delete：刪除堆頂元素；
heapify：使刪除堆頂元素的堆再次成為堆。
某些堆實現還支持其他的一些操作，如斐波那契堆支持檢查一個堆中是否存在某個元素。
算法思想
不必將值一個個地插入堆中，通過交換形成堆。假設根的左、右子樹都已是堆，並且根的元素名為R。這種情況下，有兩種可能：（1）R的值小於或等於其兩個子女，此時堆已完成；
（2）R的值大於其某一個或全部兩個子女的值，此時R應與兩個子女中值較小的一個交換，結果得到一個堆，除非R仍然大於其新子女的一個或全部的兩個。這種情況下，我們只需簡單地繼續這種將R“拉下來”的過程，直至到達某一個層使它小於它的子女，或者它成了葉結點。
篩選法
首先將要排序的所有關鍵碼放到一棵完全二叉樹的各個結點中（這時的完全二叉樹並不具備堆的特性）。顯然，所有的結點Ki都沒有子女結點，因此以這樣的Ki為根的子樹已經是堆，然後從的結點Ki開始，逐步把以為根的子樹排成堆，直到以K0為根的子樹排成堆，就完成了建堆過程。在考慮將以Ki為根的子樹排成堆時，以Ki+1，Ki+2，…，Kn-1為根的子樹已經是堆，所以這時如果有Ki≤K2i+1和Ki≤K2i+2，則不必改變任何結點的位置，以Ki為根的子樹就已經是堆；否則就要適當調整子樹中結點的位置以滿足堆的定義。由於Ki的左、右子樹都已經是堆，根結點是堆中最小的結點，所以調整後Ki的值必定是原來K2i+1和K2i+2中較小的一個。不妨假定K2+1較小，將Ki與K2i+1交換位置，這樣調整後Ki≤K2i，Ki≤K2i+1，並且以K2i+2為根的子樹原來已經是堆，不必再作任何調整，只有以K2i+1為根的子樹由於K2i+1的值已經發生變化（與Ki交換了），所以有可能不滿足堆的定義（當K2i+1的左、右子樹已經是堆）。這時可重複上述過程，考慮將K2i+1以為根的子樹排成堆。如此一層一層遞推下去，最多可以一直進行到樹葉。由於每步都保證將子樹中最小的結點交換到子樹的根部，所以這個過程是不會反饋的。它就像過篩一樣，把最小的關鍵碼一層一層選擇出來。
建堆效率
n個結點的堆，高度d=。根為第0層，則第i層結點個數為2i，考慮一個元素在堆中向下移動的距離。大約一半的結點深度為d-1，不移動（葉）。四分之一的結點深度為d-2，而它們至多能向下移動一層。樹中每向上一層，結點的數目為前一層的一半，而子樹高度加一。這種算法時間代價為Ο（n)
由於堆有logn層深，插入結點、刪除普通元素和刪除最小元素的平均時間代價和最差時間代價都是
Ο（logn）。
堆操作的具體實現
在程式中，堆用於動態分配和釋放程式所使用的對象。在以下情況中調用堆操作：1.事先不知道程式所需對象的數量和大小。
2.對象太大，不適合使用堆疊分配器。
堆使用運行期間分配給代碼和堆疊以外的部分記憶體。
傳統上，作業系統和運行時庫隨附了堆實現。當進程開始時，作業系統創建稱為進程堆的默認堆。如果沒有使用其他堆，則使用進程堆分配塊。語言運行時庫也可在一個進程內創建單獨的堆。（例如，C運行時庫創建自己的堆。）除這些專用堆外，應用程式或許多載入的動態程式庫(DLL)之一也可以創建並使用單獨的堆。Win32提供了一組豐富的API用於創建和使用專用堆。有關堆函式的優秀教程，請參閱MSDN平台SDK節點。
當應用程式或DLL創建專用堆時，這些堆駐留於進程空間中並且在進程範圍內是可訪問的。某一給定堆分配的任何數據應為同一堆所釋放。（從一個堆分配並釋放給另一個堆沒有意義。）
在所有虛擬記憶體系統中，堆位於作業系統的虛擬記憶體管理器之上。語言運行時堆也駐留在虛擬記憶體之上。某些情況下，這些堆在作業系統堆的上層，但語言運行時堆通過分配大的塊來執行自己的記憶體管理。繞開作業系統堆來使用虛擬記憶體函式可使堆更好地分配和使用塊。
典型的堆實現由前端分配器和後端分配器組成。前端分配器維護固定大小塊的自由列表。當堆收到分配調用後，它嘗試從前端列表中查找自由塊。如果此操作失敗，則堆將被迫從後端（保留和提交虛擬記憶體）分配一個大塊來滿足請求。通常的實現具有每個塊分配的開銷，這花費了執行周期，也減少了可用存儲區。
WindowsNT的實現（WindowsNT4.0版及更高版本）使用127個從8到1,024位元組不等的8位元組對齊塊的自由列表和1個混合列表。混合列表（自由列表【0】）包含大小超過1,024位元組的塊。自由列表包含在雙向連結表中連結在一起的對象。默認情況下，進程堆執行合併操作。（合併操作是組合相鄰的自由塊以生成更大的塊的操作。）合併操作花費了額外的周期，但減少了堆塊的內部碎片。
單個全局鎖可防止多執行緒同時使用堆。此鎖主要用於保護堆數據結構不受多執行緒的任意訪問。當堆操作過於頻繁時，此鎖會對性能造成負面影響。
