堆的特性：

必須是完全二叉樹
用數組實現
任一結點的值是其子樹所有結點的最大值或最小值
最大值時，稱為“最大堆”，也稱大根堆；

在完全二叉樹中，任何一個子樹的最大值都在這個子樹的根結點。

最小值時，稱為“最小堆”，也稱小根堆。

在完全二叉樹中，任何一個子樹的最小值都在這個子樹的根結點。

大根堆

小根堆

可以看到，對于**堆（Heap）**這種數據結構，從根節點到任意結點路徑上所有的結點都是有序的。

整理：
二叉堆

邏輯上：完全二叉樹
存儲上：數組（順序存儲）
作用：找最值		（優先級隊列）

操作：

1向下調整	*	（建隊，刪除）
2建堆
3向上調整  （插入）

數據結構中堆與內存堆區的區別

一、數據結構中的堆和棧

   堆和棧在數據結構中是兩種不同的數據結構。 兩者都是數據項按序排列的數據結構。棧：像是裝數據的桶或者箱子棧是大家比較熟悉的一種數據結構，它是一種具有后進先出的數據結構，也就是說后存放的先取，先存放的后取，這就類似于我們要在取放在箱子底部的東西（放進去比較早的物體），我們首先要移開壓在它上面的物體（放入比較晚的物體）。堆：像是一顆倒立的大樹堆是一種經過排序的樹形數據結構，每個節點都有一個值。通常我們所說的堆的數據結構是指二叉樹。堆的特點是根節點的值最小（或最大），且根節點的兩個樹也是一個堆。由于堆的這個特性，常用來實現優先隊列，堆的存取是隨意的，這就如同我們在圖書館的書架上取書，雖然書的擺放是有順序的，但是我們想取任意一本時不必像棧一樣，先取出前面所有的書，書架這種機制不同于箱子，我們可以直接取出我們想要的書。

二、內存分配中的堆和棧

   我們現在經常用的并不是數據結構中的堆和棧，之所以說了數據結構中的堆和棧是為了和后面將要說的堆區和棧區區別開來，請大家一定要注意。內存中的棧區處于相對較高的地址，以地址的增長方向為上的話，棧地址是向下增長的。棧中分配局部變量空間，堆區是向上增長的用于分配程序員申請的內存空間。另外還有靜態區是分配靜態變量，全局變量空間的。只讀區是分配常量和程序代碼空間的；以及其他一些分區。

來看一個很經典的例子：

main.cppint a = 0;  全局初始化區char *p1;  全局未初始化區main (){int b; 棧char  s[] = “abc”;棧char *p2; 棧char *p3 = “123456”; 123456\0 在常量區，p3 在棧區static  int c = 0； 全局（靜態）初始化區p1 = (char *)malloc(10);堆p2 = (char *)malloc (20);堆}

三 、 內存分配中棧區和堆區的區別

0、申請方式和回收方式不同

  不知道你是否有點明白了，堆和棧的第一個區別就是申請方式的不同：棧（英文名字;stack）是系統自動分配空間的

，例如我們定義了一個 char a ；系統會自動的在棧上為其開辟空間。而堆（英文名字:heap）則是程序員根據需要自己申請的空間，例如malloc(10); 開辟是個字節的空間。由于棧上的空間是自動分配自動回收的，所以棧上的數據的生存周期只是在函數的運行過程中，運行后就釋放掉，不可以再訪問。而堆上的數據只要程序員不釋放空間，就一直可以訪問到，不過缺點是一旦忘記釋放會造成內存泄露。

1、 申請后系統的響應

    棧 ： 只要棧的剩余空間大于所申請的空間，系統將為程序提供內存，否則將報異常提示棧溢出。堆：首先應該知道操作系統有一個記錄空閑內存地址的鏈表，當系統受到程序的申請時，會遍歷該鏈表，尋找第一個空間大于所申請空間的堆。結點，然后將該結點從空閑結點鏈表中刪除，并將該結點的空間分配給程序，另外，對于大多數系統，會在這塊內存空間中的首地址處記錄本次分配的大小，這樣，代碼中的delete語句才能正確的釋放本內存空間。另外，由于找到的堆結點的大小不一定正好等于申請的大小，系統會自動的將多余的那部分重新放入空閑鏈表中。也就是說堆會在申請后還要做一些后續的工作這就會引出申請效率的問題

2、申請效率的比較

棧：  由系統自動分配，速度較快。但程序員是無法控制的。堆：  是由new分配的內存，一般速度比較慢，而且容易產生內存碎片，不過用起來最方便。

3、 申請大小的限制

棧： 在Windows下，棧是向低地址擴展的數據結構，是一塊連續的內存的區域。
這句話的意思是棧頂的地址和棧的最大容量是系統預先規定好的，
在Windows下，棧的大小是2M（也有的說是1M，總之是一個編譯時就確定的常數），
如果申請的空間超過棧的剩余空間時，將提示overflow。因此，能從棧獲得的空間較小。堆：堆是向高地址擴展的數據結構，是不連續的內存區域。這是由于系統是用鏈表來存儲空閑內存地址的，自然是不連續的，而鏈表的遍歷方向是由低地址向高地址。堆的大小受限于計算機系統中有效的虛擬內存。由此可見，堆獲得的空間比較靈活，也比較大。

4、堆和棧中的內存內容

 由于棧的大小限制，所以用子函數還是有物理意義的，而不僅僅是邏輯意義。棧：在函數調用時，第一個進棧的是主函數中函數調用后的下一條指令（函數調用語句的嚇一跳可執行語句）的地址，
然后是函數的各個參數，在大多數的C編譯器中，參數是有右往左入棧的，然后是函數中的局部變量。
注意靜態變量是不入棧的。
當本次函數調用結束后，局部變量先出棧，然后是參數，最后棧頂指針指向最開始存的地址，
也就是主函數中的下一條指令，程序由該點繼續運行。

堆：一般是在堆的頭部用一個字節存放堆的大小。堆中的具體內容由程序員安排。

5、 關于堆和棧一個比較形象的比喻

棧：使用棧就像我們去飯館里吃飯，只管點菜（發出申請）、付錢、吃（使用），吃飽了就走，
不必理會切菜，洗菜等準備工作和洗碗、刷鍋等掃尾工作，他的好處就是快捷，但是自由度小。堆：使用堆就像是自己動手做喜歡的菜肴，比較麻煩，但是比較符合自己的口味，而且自由度大

此處參考了博客：http://blog.csdn.net/wolenski/article/details/7951961#comments

堆的基本操作

堆就是完全二叉樹
而完全二叉樹其實就是數組，你可以把它想象成一個完全二叉樹。在數組中定義一個規則，

規則
左 2i+1
右 2i+2
父 (i-1)/2

大根堆的向下調整

1，每回數組中進來一個樹，把它與父結點進行比較，如果比他大，就交換
2，找父結點，進來的數在數組中的下標（i-1）/2，就是父結點的位置

堆的操作

堆的向下調整

建堆

小堆的建立

從最后一個非葉子節點開始，不斷的向下調整。

向上調整