一、C++、java為什么選擇堆這種數(shù)據(jù)結(jié)構(gòu)

效率：執(zhí)行堆排序所需的時(shí)間呈對(duì)數(shù)增長(zhǎng)，而其他算法可能隨著要排序的元素?cái)?shù)量的增加而呈指數(shù)級(jí)增長(zhǎng)。這種排序算法非常有效。

內(nèi)存使用: 內(nèi)存使用是最小的，因?yàn)槌吮４嬉判虻脑氐某跏剂斜硭匦璧臇|西之外，它不需要額外的內(nèi)存空間來(lái)工作

簡(jiǎn)單性: 它比其他同樣有效的排序算法更容易理解，因?yàn)樗皇褂孟冗M(jìn)的計(jì)算機(jī)科學(xué)概念，如遞歸。

堆排序(HeapSort)基本概念

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

堆的介紹詳見數(shù)據(jù)結(jié)構(gòu)–Heap介紹及Java代碼的實(shí)現(xiàn)示例

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

堆排序是一種in-place算法，排序后，相同的元素?zé)o法保證相對(duì)的順序，即是不穩(wěn)定的。

延伸閱讀：

二、堆和棧的不同

1、分配方式不同：

棧: 由系統(tǒng)自動(dòng)分配。 例如，聲明在函數(shù)中一個(gè)局部變量 int b; 系統(tǒng)自動(dòng)在棧中為b開辟空間

堆: 需要程序員自己申請(qǐng)，并指明大小，在c中malloc函數(shù)

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

在C++中用new運(yùn)算符

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

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

2、空間大小不同：

一般來(lái)講在32位系統(tǒng)下，堆內(nèi)存可以達(dá)到4G的空間，從這個(gè)角度來(lái)看堆內(nèi)存幾乎是沒(méi)有什么限制的。但是對(duì)于棧來(lái)講，一般都是有一定的空間大小的，例如，在VC6下面，默認(rèn)的棧空間大小是1M。

3、分配效率不同：

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

4、碎片問(wèn)題：

棧：只要棧的剩余空間大于所申請(qǐng)空間，系統(tǒng)將為程序提供內(nèi)存，否則將報(bào)異常提示棧溢出。

堆：首先應(yīng)該知道操作系統(tǒng)有一個(gè)記錄空閑內(nèi)存地址的鏈表，當(dāng)系統(tǒng)收到程序的申請(qǐng)時(shí)，

會(huì)遍歷該鏈表，尋找名列前茅個(gè)空間大于所申請(qǐng)空間的堆結(jié)點(diǎn)，然后將該結(jié)點(diǎn)從空閑結(jié)點(diǎn)鏈表中刪除，并將該結(jié)點(diǎn)的空間分配給程序，另外，對(duì)于大多數(shù)系統(tǒng)，會(huì)在這塊 內(nèi)存空間中的首地址處記錄本次分配的大小，這樣，代碼中的delete語(yǔ)句才能正確的釋放本內(nèi)存空間。另外，由于找到的堆結(jié)點(diǎn)的大小不一定正好等于申請(qǐng)的 大小，系統(tǒng)會(huì)自動(dòng)的將多余的那部分重新放入空閑鏈表中。

對(duì)于堆來(lái)講，頻繁的new/delete勢(shì)必會(huì)造成內(nèi)存空間的不連續(xù)，從而造成大量的碎片，使程序效率降低。對(duì)于棧來(lái)講，則不會(huì)存在這個(gè)問(wèn)題，因?yàn)闂Ｊ窍冗M(jìn)后出的隊(duì)列，他們是如此的一一對(duì)應(yīng)，以至于永遠(yuǎn)都不可能有一個(gè)內(nèi)存塊從棧中間彈出，在他彈出之前，在他上面的后進(jìn)的棧內(nèi)容已經(jīng)被彈出。

5、生長(zhǎng)方向：

對(duì)于堆來(lái)講，生長(zhǎng)方向是向上的，也就是向著內(nèi)存地址增加的方向；對(duì)于棧來(lái)講，它的生長(zhǎng)方向是向下的，是向著內(nèi)存地址減小的方向增長(zhǎng)。

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

聲明：本站稿件版權(quán)均屬千鋒教育所有，未經(jīng)許可不得擅自轉(zhuǎn)載。