一、C++、java為什么選擇堆這種數據結構

效率：執行堆排序所需的時間呈對數增長，而其他算法可能隨著要排序的元素數量的增加而呈指數級增長。這種排序算法非常有效。

內存使用: 內存使用是最小的，因為除了保存要排序的元素的初始列表所必需的東西之外，它不需要額外的內存空間來工作

簡單性: 它比其他同樣有效的排序算法更容易理解，因為它不使用先進的計算機科學概念，如遞歸。

堆排序(HeapSort)基本概念

堆排序是一種基于二叉堆(binary heap)數據結構的基于比較的排序技術。它類似于選擇排序，先找到最小的元素，然后把最小的元素放在最開始, 然后對其余元素重復相同的過程。

堆的介紹詳見數據結構–Heap介紹及Java代碼的實現示例

由于二叉堆是一棵完整的二叉樹，所以它可以很容易地表示為數組，而基于數組的表示方式非常節省空間。如果父節點存儲在索引I，左邊的子節點可以用2 * I + 1計算，右邊的子節點可以用2 * I + 2計算(假設索引從0開始)。

堆排序是一種in-place算法，排序后，相同的元素無法保證相對的順序，即是不穩定的。

延伸閱讀：

二、堆和棧的不同

1、分配方式不同：

棧: 由系統自動分配。 例如，聲明在函數中一個局部變量 int b; 系統自動在棧中為b開辟空間

堆: 需要程序員自己申請，并指明大小，在c中malloc函數

如p1 = (char *)malloc(10);

在C++中用new運算符

如p2 = (char *)new(10);

但是注意p1、p2本身是在棧中的。

2、空間大小不同：

一般來講在32位系統下，堆內存可以達到4G的空間，從這個角度來看堆內存幾乎是沒有什么限制的。但是對于棧來講，一般都是有一定的空間大小的，例如，在VC6下面，默認的棧空間大小是1M。

3、分配效率不同：

棧是機器系統提供的數據結構，計算機會在底層對棧提供支持：分配專門的寄存器存放棧的地址，壓棧出棧都有專門的指令執 行，這就決定了棧的效率比較高。堆則是C/C++函數庫提供的，它的機制是很復雜的，例如為了分配一塊內存，庫函數會按照一定的算法（具體的算法可以參考 數據結構/操作系統）在堆內存中搜索可用的足夠大小的空間，如果沒有足夠大小的空間（可能是由于內存碎片太多），就有可能調用系統功能去增加程序數據段的 內存空間，這樣就有機會分到足夠大小的內存，然后進行返回。顯然，堆的效率比棧要低得多。

4、碎片問題：

棧：只要棧的剩余空間大于所申請空間，系統將為程序提供內存，否則將報異常提示棧溢出。

堆：首先應該知道操作系統有一個記錄空閑內存地址的鏈表，當系統收到程序的申請時，

會遍歷該鏈表，尋找名列前茅個空間大于所申請空間的堆結點，然后將該結點從空閑結點鏈表中刪除，并將該結點的空間分配給程序，另外，對于大多數系統，會在這塊 內存空間中的首地址處記錄本次分配的大小，這樣，代碼中的delete語句才能正確的釋放本內存空間。另外，由于找到的堆結點的大小不一定正好等于申請的 大小，系統會自動的將多余的那部分重新放入空閑鏈表中。

對于堆來講，頻繁的new/delete勢必會造成內存空間的不連續，從而造成大量的碎片，使程序效率降低。對于棧來講，則不會存在這個問題，因為棧是先進后出的隊列，他們是如此的一一對應，以至于永遠都不可能有一個內存塊從棧中間彈出，在他彈出之前，在他上面的后進的棧內容已經被彈出。

5、生長方向：

對于堆來講，生長方向是向上的，也就是向著內存地址增加的方向；對于棧來講，它的生長方向是向下的，是向著內存地址減小的方向增長。

堆和棧相比，由于大量new/delete的使用，容易造成大量的內存碎片；由于沒有專門的系統支持，效率很低；由于可能引發用戶態和核心態的切換，內存的申請，代價變得更加昂貴。所以棧在程序中是應用較廣泛的，就算是函數的調用也利用棧去完成，函數調用過程中的參數，返回地址，EBP和局部變量都采用棧的方式存放。所以，我們推薦大家盡量用棧，而不是用堆。雖然棧有如此眾多的好處，但是由于和堆相比不是那么靈活，有時候分配大量的內存空間，還是用堆好一些。

聲明：本站稿件版權均屬千鋒教育所有，未經許可不得擅自轉載。