怎麼存儲堆

① 什麼事堆棧,堆棧有哪些運算,堆棧怎樣存儲

stack,其實就是一塊內存空間,關鍵在於他的用途.
1.對於程序指令來說
執行exe時,程序都會默認分配1M堆棧空間,vs2008等開發軟體都可以進行調整實際大小.
指令變成一條條機器碼,cpu會一條條執行.
例子:
xxxxxxx
call 0x403650 <- --
yyyyy
在執行call命令時,cpu會把下一條指令地址寫入堆棧地址空間中,當然也包括其他信息.
0x403650相當於一個子程序的地址,完事後,必然有一個ret之類的指令.這時,cpu根據先前保存的地址,也就是yyyyy這條指令所對應的地址.這樣就能繼續往下執行了.
關於這一點,用ollydbg好好玩一下,馬上就清楚了.

2.一般的應用程序編寫.
我們在編寫程序時,有時採用堆棧結構,有時採用隊列結構,這跟所採用的演算法有很大關系.
最常見的遞歸演算法,按遞歸展開的話,所有的細節就跟第1點完全一樣,好處是,大都程序員根本不關心象第1點所描述的細節.只知道其調用過程和最終執行結果.具體細節可能就不關心了.

當把遞歸演算法 用非遞歸演算法寫時,很可能你就要引入堆棧結構(其實就是人為手動申請一個內存空間,比如buffer[遞歸最深層數], 這樣,就可以編寫出直觀的順序結構的代碼. cpu也不用著因調用子程序,一次次把相關信息寫入系統的堆棧中(第1點所說)..因為buffer[]的存在就是為了避免這種情況.

--------------------
stack最常用兩種操作,push和pop. 你可以用c或是c++ 標准庫提供的實現.
如果不是大工程,基本上沒必要這么做.
搞個數組 buf[], 再搞個索引變數int index,用來指示top位置. 寫入數據時,index++,取出數據時index--

3.最常用的,但易忽略的.
平常所說的,局部變數就是在堆棧中分配的.所以他出了作用域就自動釋放了.
c語言很容易理解,不容易出錯.
但c++中,編譯器有不同的策略.
比如
CTeacher t= bar();
--
CTeacher bar()
{
CTeacher xx;
為CTeacher的成員賦值
return xx.
}
你一定為這里xx對象是局部變數,出了函數作用域,對應的內存主釋放了.
CTeacher t= bar();
因為bar()是返回一個Cteacher對象,所以這里就要執行拷貝構造函數,
你會奇怪,問題是bar()返回的對象是無效的.但執行卻不會出錯.
為什麼?
首先對堆棧的理解是對.只是c++編譯器內部會改寫bar()這個函數.
變成 void bar(CTeacher& tmp)
這樣,t就作為引用參數傳入了,函數內部創建臨時對象,然後賦值給引用對象就成了.結果當然正確了.

4. 是第2點的延伸,相當重要.
一些大的應用工程,往往配合堆來對內存進行管理.
以後你接觸一些第三方程序,一定會奇怪,要動態申請內存,直接new或malloc一個對象不就行了么,為什麼要這么麻煩.
其中一個重要原因:減少碎片,提高內存使用效率.
你先申請大的空間(new/malloc),然後藉助stack的特性來管理和控制這塊空間!!!
-------------------------------

ps:理解到這幾層差不多夠用了

② 堆和堆排序

1，堆是一個完全二叉樹；
完全二叉樹要求除了最後一層，其他層的節點都是滿的，最後一層的節點都靠左排列。
2，堆中每個節點都必須大於等於（或小於等於）其子樹中每個節點的值。
堆中每個節點的值都大於等於（或者小於等於）其左右子節點的值。
3，對於每個節點的值都大於等於子樹中每個節點值的堆，叫作「大頂堆」。對於每個節點的值都小於等於子樹中每個節點值的堆，叫「小頂堆」。

要實現一個堆，要先知道堆都支持哪些操作，已及如何存儲一個堆。
1，如何存儲一個堆：
完全二叉樹比較適合用數組來存儲。用數組來存儲完全二叉樹是非常節省存儲空間的。因為不需要存儲左右子節點的指針，單純地通過數組的下標，就可以找到一個節點的左右子節點和父節點。
2，往堆中插入一個元素
往堆中插入一個元素後，需要繼續滿足堆的兩個特性
（1）如果把新插入的元素放到堆的最後，則不符合堆的特性了，於是需要進行調整，讓其重新滿足堆的特性，這個過程叫做 堆化（heapify）
（2）堆化實際上有兩種，從下往上和從上往下
（3）從下往上的堆化方法：
堆化非常簡單，就是順著節點所在的路徑，向上或者向下，對比，然後交換。

（1）從堆的定義的第二條中，任何節點的值都大於等於（或小於等於）子樹節點的值，則堆頂元素存儲的就是堆中數據的最大值或最小值。
（2）假設是大頂堆，堆堆頂元素就是最大的元素，但刪除堆頂元素之後，就需要把第二大元素放到堆頂，那第二大元素肯定會出現在左右子節點中。然後在迭代地刪除第二大節點，以此類推，直到葉子節點被刪除。

但這種方式會使堆化出來的堆不滿足完全二叉樹的特性
（3）可以把最後一個節點放到堆頂，然後利用同樣的父子節點對比方法，對於不滿足父子節點大小關系的，互換兩個節點，並且重復進行這個過程，直到父子節點之間滿足大小關系為止，這是從上往下的堆化方法。

一個包含n個節點的完全二叉樹，樹的高度不會超過log2n。堆化的過程是順著節點所在路徑比較交換的，所以堆化的時間復雜度跟樹的高度成正比，即O(log n)。插入數據和刪除堆頂元素的主要邏輯就是堆化，所以往堆中插入一個元素和刪除堆頂元素的時間復雜度都是O(log n)。

（1）排序方法有時間復雜度是O(n^2)的冒泡排序，插入排序，選擇排序，有時間復雜度是O（nlogn）的歸並排序，快速排序，線性排序。

（2）藉助堆這種數據結構實現的排序演算法就叫作堆排序，這種排序方法的時間復雜度非常穩定，是O(nlogn)，並且它還是原地排序演算法。
堆排序的過程大致分解為兩大步驟：建堆和排序
（3）建堆：
1，首先將數組原地建成一個堆。「原地」：是指不藉助另一個數組，就在原地數組上操作。
2，建堆有兩種思路：
第一種：在堆中插入一個元素的思路。
盡管數組中包含n個數據，但是可以假設起初堆中只包含一個數據，就是下標為1的數據。然後，調用插入方法，將將下標從2到n的數據依次插入到堆中，這樣就將包含n個數據的數組，組織成了堆
第二種：是從後往前處理數組，並且每個數據都是從上往下堆化。
第二種和第一種思路截然相反，第一種建堆思路的處理過程是從前往後處理數據，並且每個數據插入堆中時，都是從下往上堆化。
對下標從n/2開始到1的數據進行堆化，下標是n/2 + 1到n的節點，是葉子節點，不需堆化
3，建堆的時間復雜度
每個節點堆化的時間復雜度是O(logn)，則n/2+1個節點堆化的總時間復雜度是O(n)。
①：因為葉子節點不需要堆化，所以需要堆化的節點從倒數第二層開始。每個節點堆化的過程中，需要比較和交換的節點個數，跟這個節點高度k成正比。
（4）排序：
建堆結束後，數組中的數據已是按照大頂堆的特性來組織的。數組中的第一個元素就是堆頂，也就是最大的元素。
將它和最後一個元素交換，最大元素就放到了下標為n的位置
這個過程有點類似「刪除堆頂元素」的操作，當堆頂元素移除後，把下標為n的元素放到堆頂，然後在通過堆化的方法，將剩下的n-1個元素重新構建成堆。堆化完成之後，在取堆頂元素，放到下標是n-1的位置，一直重復這個過程，直到最後堆中只剩下標為1的一個元素，排序工作就完成了。

（5）時間，空間復雜度，以及穩定性分析
①：整個堆排序的過程，都只需要極個別臨時存儲空間，所以堆排序是原地排序演算法。
②：堆排序包括建堆和排序兩個操作，建堆過程的時間復雜度是O(n)，排序過程的時間復雜度是O(nlogn),所以堆排序的時間復雜度是O(nlogn)
③：堆排序不是穩定的排序演算法，可能改變值相等的數據原始相對順序。