?heap
heap發(fā)音
英：[hi:p] 美：[hip]
英： 美：
heap中文意思翻譯
vt.使成堆, 裝滿, 大量給予
n.堆, 許多, <口>破車
heap詞形變化
動詞第三人稱單數(shù): heaps |動詞過去式: heaped |動詞過去分詞: heaped |動詞現(xiàn)在分詞: heaping |
heap短語詞組
knock/strike all of a heap
1. 使大吃一驚; 把……弄糊涂
He was struck all of a heap when he heard of their generosity to him.
聽到他們對他如此慷慨仁慈, 他給搞糊涂了。
heap習(xí)慣用語
heap特殊用法
heap常見例句
1 、There is a heap of waste material in front of the laboratory.───實驗室前面有一堆廢料。
2 、He was struck all of a heap when he heard of their hostility toward him.───聽說他們恨他，他大吃一驚。
3 、The decision to close the factory has consigned6000 people to the scrap heap.───關(guān)閉那家工廠的決定使 6000 人遭到了遺棄。
4 、OFF has no effect on a heap.───OFF對堆沒有影響。
5 、His sole object was to heap up riches .───他的唯一目的就是聚積財富。
6 、They heap much food on my plate beyond I can eat.───他們在我的盤子上堆了很多食物，我吃都吃不完。
7 、We found you in a trash heap.───你是從垃圾堆里撿的。
8 、She piled the papers in a heap on her desk, just anyhow.───她把文件在桌上隨便擱成一堆。
9 、If you're not ready, he goes to the back of the heap.─── 如果你沒準(zhǔn)備好 他就得回拘留所
10 、Java applications can also be sensitive to the Java heap size.───Java應(yīng)用程序也可能對Java堆的大小敏感。
11 、He was chucked all of a heap at first sight of her.───他一看到她就被迷住了。
12 、They collected fallen leaves into a heap.───他們把落葉歸成一堆。
13 、To be in a heap or pile,as leaves for decomposition or fermentation.───使成堆成堆或團(tuán)，例如樹葉堆積起來分解或發(fā)酵。
14 、They heap pity on the disabled, smother them in charity.───他們對于殘廢的人憐憫有加，慷慨施舍。
15 、It was in the rubbish heap about to be incinerated.─── 它就在即將被焚燒的垃圾堆里
16 、Modify your application to look for a NULL heap name.───修改應(yīng)用程序以查找NULL堆名。
17 、I found her on top of the heap of innocent villagers.─── 我在無辜村民的尸體堆上找到了她
18 、The heap. The heap is a big block of memory used for allocating.───heap是用來在運行時對占用內(nèi)存小的變量進(jìn)行分配的大塊內(nèi)存。
19 、He goes there a heap too often.───他到那兒去得太多了。
20 、And they gathered them together, heap after heap, and the land stank.───14眾人把青蛙聚攏成堆，遍地都發(fā)臭了。
21 、Can you tell how many jin of tomatoes there are in this heap?───你估一估這堆西紅柿有幾斤。
22 、How can I set the Java Memory heap for Tomcat?───原 Tomcat 在linux下如何設(shè)置內(nèi)存大??？
23 、Ready to get off this heap, back to civilized life?───你準(zhǔn)備離開這個破船回到文明生活嗎?
24 、Can you tell how many jin of apples there are in this heap?───你估一估這堆蘋果有幾斤。
25 、Never seen such a sorry-lookin' heap of maggot shit in my life.───“這輩子沒見過一堆長得這么爛的人！”
26 、Or a heaping bounty that you must reap for yourself.─── 還是你得要 親自去贏取的一大筆賞金
27 、Before the heap object is freed.───在堆對象被釋放之前就被添加到它的。
28 、So the scraps were thrown on to the waste heap.───于是這些碎片被扔進(jìn)了廢品堆。
29 、The gardener began to heap up the fallen leaves.───園丁開始把落葉堆起來。
30 、In Old China, the society was disunited, like a heap of loose sand.───四分五裂，一盤散沙，是近代舊中國社會的真實寫照。
31 、Heap, compresa una rocaille, mettere rocce.───包括堆假山，擺石塊。
32 、But the harvest is a heap on a day of sickness And incurable pain.───但在憂患、傷痛無法醫(yī)治的日子，所收割的不過一小堆。
33 、You do know a heap of people,don't you?───你認(rèn)識很多人，不是嗎?
34 、Thus,there's a great deal of flexibility in using storage on the heap.───因此，用堆保存數(shù)據(jù)時會得到更大的靈活性。
35 、I would take that with a heaping pile of salt.─── 我可不敢保證他說的都是事實
36 、Oh, mate, there's heaps, heaps of them here.─── 伙計 這里很多人都是這樣
37 、Epoxy has a limit of 10 processes per heap.───Epoxy的限制是每個堆10個進(jìn)程。
38 、I deserve a heaping portion because I'm heapingly adorable.─── 我理當(dāng)多吃點 因為我非?？蓯?/p>
39 、He put the cardboard boxes in a heap and stamped them down.───他把紙板箱堆成一堆, 將它們踩扁。
40 、You'd better not heap up your problems that you should solve.───你不要把你該解決的問題積在一起。
41 、To define the setting of heap size in WebSphere.───The page path is 服務(wù)器>應(yīng)用程序服務(wù)器>Server1>Java和進(jìn)程管理>進(jìn)程定義>Java虛擬機.Set the 初始堆大小 and 最大堆大小。
42 、Meatball that he would "heap additives" meatball.───他將這種肉丸稱為“添加劑堆”的肉丸。
43 、Thy belly is like a heap of wheat, set about with lilies.───你的腰如一堆麥子,周圍有百合花。
44 、Home, I seem to be busy catching up or just collapsing in a heap for.───回家后，我似乎整天都忙于補瞌睡，要么就是不擇地點地一坐下來就打盹。
45 、Object stored on the native heap.───不對存儲在本機堆上的。
46 、For a heap, a row locator is a pointer to the row.───對于堆,行**器是指向行的指針。
47 、There was a heap of garbage piled next to the road.───在路旁堆有一堆垃圾。
48 、DROP INDEX new heap rebuild (if applicable).───DROP INDEX新堆重新生成(如果適用)。
49 、A quantity of objects stacked or thrown together in a heap.───一堆，一疊按堆排放或扔在一起的一些東西
50 、You have no right to heap insults on anybody.───他沒有權(quán)力侮辱任何一個人。
51 、Cover the heap of straw when it rains.───下雨時要把草堆蓋上。
52 、I was nothing more than a groaning heap in the corner.─── 我只是蜷縮在角落里*著
53 、I have heaps of plans. I have so many plans.─── 我有成堆的計劃 超多計劃
54 、He found a toy electric motor in a junk heap.───他在廢物堆里找到了一臺玩具電動機。
55 、Don't throw your book into the rubbish heap.───不要把你的書扔進(jìn)垃圾堆。
56 、The number of times the garbage collector has compacted the heap.───垃圾回收器已壓縮堆的次數(shù)。
57 、He was knocked all of a heap when he heard of their generosity to him.───聽到他們對他如此慷慨仁慈,他給搞糊涂了。
58 、Before GC started, 11536 Kb of heap space was in use.───在GC開始之前,使用了11536 Kb的堆空間。
59 、That garbage heap is an eyesore in such a beautiful scenic spot.───在風(fēng)景如此優(yōu)美的地方有堆垃圾，真是有礙觀瞻。
60 、Value types are stored on the stack, not the heap.───值類型存儲在堆棧中,而不是堆中。
61 、Their papers were mixed up in a heap on the desk.───他們的論文在課桌上亂成一堆。
62 、This heap doesn't run on *iles and rainbows.─── 這破船又不是靠微笑和彩虹跑起來的
63 、Use and heap headdress of yarn skills.───頭飾的使用及堆紗的技巧。
64 、The books lay in a heap on the floor.───書堆放在地板上。
65 、She did not shuffle them to a heap.───她并沒有把它們拼湊成一堆。
66 、A heap of old clothes was lying in the corner.───一堆舊衣服堆在角落里。
67 、A small heap, pile, or mound.───一堆，一疊，小丘
68 、He fall down the stairs, landing in a heap at the bottom.───他從樓梯上摔下來，直跌到樓梯底部滾成一團(tuán)。
69 、He was struck all of a heap on her change in attitude.───她態(tài)度的變化，讓他摸不著頭腦。
70 、The best interest she likes is to heap up dollars.───她的最大嗜好就是攢錢。
71 、A raised mass, as of hay; a heap.───堆一堆堆起來的東西，如草垛; 堆
72 、She could see the tall runway and the heap of earth and coal cast out.───她可以看到高高的滑槽和一堆堆挖出的泥土和煤。
73 、They collected the fallen leaves into a heap.───他們把落葉掃集在一起。
74 、Alex owned a whole heap of ferrets.───亞歷克斯養(yǎng)著一大群白鼬。
75 、A confused or jumbled mass; a heap.───大團(tuán)，大塊；一堆雜亂混雜的一團(tuán)；一堆
76 、Unluckily, it was a heap of dead rabbits.───倒霉，原來那是堆死兔子。
77 、His books lay in a heap on the floor of the living room.───他的書疊成一堆放在客廳的地板上。
78 、Converts a heap into a sorted range.───堆的排序。
79 、I then collapsed in an undignified heap.───回到家里，我整個人一下就癱軟在地。
80 、The books lay all together in a heap.───書都堆在一起。
81 、The spur was forthwith transferred to the heap.───一眨眼這馬刺就進(jìn)入了那堆破爛里。
82 、To form into a hill, pile, or heap.───堆起，壘起，疊起
83 、His clothes lay in a heap on the floor.───他的衣服堆在地板上。
84 、Clouds heap upon clouds and it darkens.───云霾堆積，黑暗漸深。
85 、All his clothes are in a heap.───他的衣服統(tǒng)統(tǒng)堆在地板上。
86 、There is a disorderly heap of clothes in his room.───他屋里有一堆亂七八糟的衣服。
87 、He collapsed in a heap on the floor.───他重重地倒在地板上。
88 、Aren't you going to heap the blame on me?───你不準(zhǔn)備責(zé)怪我嗎?
89 、A raised mass, as of hay;a heap.───堆一堆堆起來的東西，如草垛；堆
90 、Don't heap insult on insult.───不要屢受侮辱。
數(shù)據(jù)結(jié)構(gòu)堆（優(yōu)先隊列）：二叉堆、d堆、左式堆、斜堆與二項隊列
這是數(shù)據(jù)結(jié)構(gòu)類重新復(fù)習(xí)筆記的第 五 篇，同專題的其他文章可以移步： https://www.jianshu.com/nb/39256701
堆 （Heap）又稱為 優(yōu)先隊列 （priority queue），在隊列的基礎(chǔ)上，堆允許所有隊列中的元素不一定按照 先進(jìn)先出 （FIFO）的規(guī)則進(jìn)行，而是使得每個元素有一定的優(yōu)先級，優(yōu)先級高的先出隊列。
優(yōu)先隊列至少存在兩個重要的操作：
有幾種簡單而明顯的方法實現(xiàn)優(yōu)先隊列。
二叉堆 （binary heap）是一種對于優(yōu)先隊列的實現(xiàn)，可以簡稱為堆
堆是一棵 完全二叉樹 （complete binary tree），即所有節(jié)點都必須有左右兩個子節(jié)點，除了最后一排元素從左向右填入，直到?jīng)]有元素為止。
很顯然，一棵高為h的完全二叉樹有 2^h 到 2^(h+1)-1 個節(jié)點，即其高度為 logN 向下取整。
完全二叉樹的好處在于其規(guī)律性，可以使用一個數(shù)組而不需要鏈表來表示
對于數(shù)組中任一位置 i 上的元素，其左兒子在位置 2i 上，右兒子在左兒子后的單元 (2i+1) 上，它的父親則在位置 i/2 向下取整上。
因此，不僅不需要鏈，而且遍歷該樹所需要的操作也極簡單，在大部分計算機上都可能運行得非?？?。唯一問題是最大的堆的大小需要事先估計。
使操作可以快速執(zhí)行的性質(zhì)是 堆序性質(zhì) （heap-order property）：對于每一個節(jié)點X，X的父節(jié)點中的鍵小于等于X中的鍵，除沒有父節(jié)點根節(jié)點外。
將待**入的元素首先放置在最后一個位置上，以保證他是一個完全二叉樹，然后將該元素與其父節(jié)點（i/2向下取整）比較，如果比其父節(jié)點小，就將兩者互換，互換后再和新的父節(jié)點比較，這種方式稱為 上濾 （percolate up），得到一個小頂堆（min heap），如果比較的時候是較大的值向上走，就會得到一個大頂堆（max heap）
比如向一個小頂堆中**入元素14的操作：
找出、返回并刪除最小元非常簡單，最小元就是根節(jié)點處的元素，將其返回并刪除。接下來是處理這個B。首先拿下最后一個元素X，如果元素X比B的兩個子節(jié)點都小，可以直接將X**入到B的位置，如果X比B的兩個子節(jié)點中的任意一個大，就不能**入，此時找到兩個子節(jié)點中較小的那個放到B處，B轉(zhuǎn)而移至這個子結(jié)點處。重復(fù)如上的步驟直到X可以**入B處為止。這個操作成為 下濾 （percolate down）
比如從一個小頂堆中刪除根節(jié)點
decreaseKey(p, A) 操作減小在位置p處的元素的值，減少量為A，可以理解為調(diào)高了某個元素的優(yōu)先級。操作破壞了堆的性質(zhì)，從而需要上濾操作進(jìn)行堆的調(diào)整。
increaseKey(p, A) 操作增加在位置p處的元素的值，增加量為A，可以理解為降低了某個元素的優(yōu)先級。操作破壞了堆的性質(zhì)，從而需要下濾操作進(jìn)行堆的調(diào)整。
remove(p) 操作刪除在堆中位置p處的節(jié)點，這種操作可以通過連續(xù)執(zhí)行 decreaseKey(p, ∞) 和 deleteMin() 完成，可以理解馬上刪除某個一般優(yōu)先級的元素
即將一個原始集合構(gòu)建成二叉堆，這個構(gòu)造過程即進(jìn)行N次連續(xù)的 insert 操作完成
定理 ：包含 2^(h+1)-1 個節(jié)點且高度為h的理想二叉樹（perfect binary tree）的節(jié)點的高度和為 2^(h+1)-1-(h+1)
d堆 （d-Heaps）是二叉堆的簡單**，它與二叉堆很像，但是每個節(jié)點都有d個子節(jié)點，所以二叉堆是d為2的d堆。d堆是完全d叉樹。比如下邊的一個3堆。
d堆比二叉堆淺很多，其insert的運行時間改進(jìn)到 O(logdN) 。但是deleteMin操作比較費時，因為要在d個子節(jié)點中找到最小的一個，需要進(jìn)行d-1次比較。d堆無法進(jìn)行find操作，而且將兩個堆合二為一是很困難的事情，這個附加操作為merge合并。
注意！ 在尋找節(jié)點的父節(jié)點、子節(jié)點的時候，乘法和除法都有因子d。如果d是一個2的冪，則可以通過使用二進(jìn)制的 移位 操作計算，這在計算機中是非常省時間的。但是如果d不是一個2的冪，則使用一般的乘除法計算，時間開銷會急劇增加。有證據(jù)顯示，實踐中，堆可以勝過二叉堆
這些高級的數(shù)據(jù)結(jié)構(gòu)很難使用一個數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，所以一般都要用到鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)可能會使得其操作變慢。
零路徑長 （null path length）npl(X)：定義為從一個X節(jié)點到其不具有兩個子節(jié)點的子節(jié)點的最短路徑長，即具有0個或者1個子節(jié)點的節(jié)點npl=0，npl(null)=-1，任意節(jié)點的零路徑長都比其各個子節(jié)點中零路徑長最小值多1。
左式堆 （leftist heap）是指對于任意一個節(jié)點X，其左子節(jié)點的零路徑長都大于等于其右子節(jié)點的零路徑長。很顯然，左式堆趨向于加深左路徑。比如下邊的兩個堆，只有左邊的是左式堆，堆的節(jié)點標(biāo)示的是該節(jié)點的零路徑長。
左式堆的實現(xiàn)中，需要有四個值：數(shù)據(jù)、左指針、右指針和零路徑長。
定理 ：在右路徑上有r個節(jié)點的左式堆必然至少有 2^r-1 個節(jié)點
merge 是左式堆的基本操作， insert **入可以看成是一個單節(jié)點的堆與一個大堆的 merge ， deleteMin 刪除最小值操作可以看成是首先返回、刪除根節(jié)點，然后將根節(jié)點的左右子樹進(jìn)行 merge 。所以 merge 是左式堆的基本操作。
假設(shè)現(xiàn)在有兩個非空的左式堆H1和H2，merge操作遞歸地進(jìn)行如下的步驟：
例如如下的兩個堆：
將H2與H1的右子樹（8--17--26）進(jìn)行merge操作，此時（8--17--26）和H2的merge操作中又需要（8--17--26）和H2的右子堆（7--37--18）進(jìn)行merge操作……如此遞歸得到如下的堆：
然后根據(jù)遞歸的最外層（回到H1和H2的merge的第二步），將上邊合并的堆成為H1的右子堆
此時根節(jié)點（3）處出現(xiàn)了左右子堆不符合左式堆的情況，互換左右子堆并更新零路徑長的值
斜堆 （skew heap）是左式堆的自調(diào)節(jié)形式，實現(xiàn)起來極其簡單。斜堆和左式堆的關(guān)系類似于伸展樹和AVL樹之間的關(guān)系。斜堆是具有堆序的二叉樹，但是不存在對樹的結(jié)構(gòu)的現(xiàn)限制。不同于左式堆，關(guān)于任意結(jié)點的零路徑長的任何信息都不保留。斜堆的右路徑在任何時刻都可以任意長，因此，所有操作的最壞情形運行時間均為O(N)。然而，正如伸展樹一樣，可以證明對任意M次連續(xù)操作，總的最壞情形運行時間是 O(MlogN)。因此，斜堆每次操作的 攤還開銷 （amortized cost）為O(logN)
斜堆的基本操作也是merge合并，和左式堆的合并相同，但是不需要對不滿足左右子堆的左式堆條件的節(jié)點進(jìn)行左右子堆的交換。斜堆的交換是無條件的，除右路徑上所有節(jié)點的最大者不交換它的左右兒子外，都要進(jìn)行這種交換。
比如將上述的H1和H2進(jìn)行merge合并操作
首先進(jìn)行第一步，除了交換左右子樹的操作與左式堆不同，其他的操作都相同
將合并的堆作為H1的右子堆并交換左右子堆，得到合并后的斜堆
二項隊列 （binomial queue）支持merge、insert和deleteMin三種操作，并且每次操作的最壞情形運行時間為O(logN)，**入操作平均花費常數(shù)時間。
二項隊列不是一棵堆序的樹，而是堆序的樹的集合，成為 森林 （forest）。堆序樹中的每一棵都是有約束的 二項樹 （binomial tree）。二項樹是每一個高度上至多存在一棵二項樹。高度為0的二項樹是一棵單節(jié)點樹，高度為k的二項樹Bk通過將一棵二項樹Bk-1附接到另一棵二項樹Bk-1的根上而構(gòu)成的。如下圖的二項樹B0、B1、B2、B3和B4。
可以看到二項樹Bk由一個帶有兒子B0，B1，……，Bk-1的根組成。高度為k的二項樹恰好有2^k個節(jié)點，而在深度d處的節(jié)點數(shù)為二項系數(shù)Cdk。
我們可以使用二項樹的集合唯一地表示任意大小的優(yōu)先隊列。以大小為13的隊列為例，13的二進(jìn)制表示為1101，從而我們可以使用二項樹森林B3、B2、B0表示，即二進(jìn)制表示的數(shù)中，第k位為1表示Bk樹出現(xiàn)，第k位為0表示Bk樹不出現(xiàn)。比如上述的堆H1和堆H2可以表示為如下的兩個二項隊列：
二項隊列額merge合并操作非常簡單，以上邊的二項隊列H1、H2為例。需要將其合并成一個大小為13的隊列，即B3、B2、B0。
首先H2中有一個B0，H1中沒有，所以H2中的B0可以直接作為新的隊列的B0的樹
其次H1和H2中兩個B1的樹可以合并成一個新的B2的樹，只需要將其中根節(jié)點較小的堆掛到根節(jié)點較大的堆的根節(jié)點上。這樣就得到了三棵B2堆，將其中根節(jié)點最大的堆直接放到新隊列中成為它的B2堆。
最后將兩個B2堆合并成一個新隊列中的B3堆。
二項隊列的deleteMin很簡單，只需要比較隊列中所有二項堆的根節(jié)點，返回和刪除最小的值即可，時間復(fù)雜度為O(logN)，然后進(jìn)行一次merge操作，也可以使用一個單獨的空間每次記錄最小值，這樣就可以以O(shè)(1)的時間返回。
森林中樹的實現(xiàn)采用“左子右兄弟”的表示方法，然后二項隊列可以使用一個數(shù)組來記錄森林中每個樹的根節(jié)點。
例如上邊的合成的二項隊列可以表示成如下的樣子：
STL中，二叉堆是通過 priority_queue 模板類實現(xiàn)的，在頭文件 queue 中，STL實現(xiàn)一個大頂堆而不是小頂堆，其關(guān)鍵的成員函數(shù)如下：
堆(heap)和棧(Stack)的區(qū)別是什么為什么平時都把堆棧放在一起講
程序的運行場所是內(nèi)存，棧和堆是進(jìn)程的虛擬內(nèi)存中的兩部分區(qū)域。
當(dāng)程序被執(zhí)行時，程序代碼，你所創(chuàng)建的變量、常量等都會被壓入?？臻g里，棧是程序代碼的執(zhí)行區(qū)域。棧的內(nèi)存地址是連續(xù)的且被一一記錄，所以說當(dāng)你創(chuàng)建了一個變量(比如int var = 1)，我們就可以通過var這個變量來訪問變量的內(nèi)容。在這里，var就存放在棧中，它的地址已經(jīng)默認(rèn)被編譯器計算好了，調(diào)用過程也不需要你涉及到有關(guān)地址的操作。更直觀的感受是數(shù)組，數(shù)組里的元素在棧里面是連續(xù)排放的，相鄰兩個元素的地址相差1。
而堆是不同于棧的另一部分區(qū)域，系統(tǒng)會給每個程序分配一部分?？臻g讓他們能夠運行起來，問題就是?？臻g必然存在不夠用的問題，而堆不屬于程序，堆是獨立的，是公用的。只要你malloc(sizeof(SIZE_YOU_WANT))，就可以得到相應(yīng)一部分的堆空間。
有棧，為什么用堆？
：棧里面的東西有生命周期，說俗點就是變量作用域，你在函數(shù)內(nèi)部創(chuàng)建一個變量，函數(shù)調(diào)用結(jié)束這個變量就沒了。而堆里面的東西獨立于你的程序，malloc()之后，除非你free()掉，否則一直存在。
為什么用堆少？
：麻煩！
有什么要注意？
：堆里面申請的東西，是隨機分配的，不像棧里面的地址都已經(jīng)計算好了。所以申請了堆空間之后一定要創(chuàng)建一個指針保存你說申請到的堆空間的地址。不然就找不到你申請的空間了。
既然涉及到指針，請注意用之前檢查一下指針空不空的問題。
堆空間的東西申請好，在用完之后一定要free()掉，以防止堆溢出。
說到安全性，還真是挺麻煩的。（純手打）