一、堆和樹的區(qū)別

1、節(jié)點(diǎn)的順序

在二叉搜索樹中，左子節(jié)點(diǎn)必須比父節(jié)點(diǎn)小，右子節(jié)點(diǎn)必須必比父節(jié)點(diǎn)大。但是在堆中并非如此。在最大堆中兩個子節(jié)點(diǎn)都必須比父節(jié)點(diǎn)小，而在最小堆中，它們都必須比父節(jié)點(diǎn)大。

2、內(nèi)存占用

普通樹占用的內(nèi)存空間比它們存儲的數(shù)據(jù)要多。你必須為節(jié)點(diǎn)對象以及左/右子節(jié)點(diǎn)指針分配額外內(nèi)存。堆僅僅使用一個數(shù)據(jù)來存儲數(shù)組，且不使用指針。

3、平衡

二叉搜索樹必須是“平衡”的情況下，其大部分操作的復(fù)雜度才能達(dá)到O(log n)。你可以按任意順序位置插入/刪除數(shù)據(jù)，或者使用 AVL 樹或者紅黑樹，但是在堆中實(shí)際上不需要整棵樹都是有序的。我們只需要滿足對屬性即可，所以在堆中平衡不是問題。因?yàn)槎阎袛?shù)據(jù)的組織方式可以保證O(log n) 的性能。

4、搜索

在二叉樹中搜索會很快，但是在堆中搜索會很慢。在堆中搜索不是名列前茅優(yōu)先級，因?yàn)槭褂枚训哪康氖菍⒆畲螅ɑ蛘咦钚。┑墓?jié)點(diǎn)放在最前面，從而快速的進(jìn)行相關(guān)插入、刪除操作。

延伸閱讀：

二、堆排序（Heap Sort）

堆排序的基本思想是：將待排序序列構(gòu)造成一個大頂堆，此時，整個序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次大值。如此反復(fù)執(zhí)行，便能得到一個有序序列了。

1.構(gòu)造初始堆。將給定無序序列構(gòu)造成一個大頂堆（一般升序采用大頂堆，降序采用小頂堆)。

看堆頂?shù)男蛱枺瑏砼袛嗝星懊﹤€非葉子節(jié)點(diǎn)的索引。這點(diǎn)很重要!

2.此時我們從最后一個非葉子結(jié)點(diǎn)開始,從左至右，從下至上進(jìn)行調(diào)整。

調(diào)整就是找每個非葉子節(jié)點(diǎn)的葉子節(jié)點(diǎn)是不是比他大,把大的交換上來,這一層交換結(jié)束再交換上一層,直到使根節(jié)點(diǎn)即堆頂元素為最大值。

這里要注意，如果上一層交換之后，當(dāng)前層又不滿足堆的要求，繼續(xù)交換。

3. 將堆頂元素與末尾元素進(jìn)行交換，使末尾元素最大。然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復(fù)進(jìn)行交換、重建、交換。

也就是說每一層堆頂與末尾交換，都能得到一個當(dāng)前的最大值，放在有序數(shù)組的最后面相當(dāng)于！然后從后往前填充為有序數(shù)組。

再簡單總結(jié)下堆排序的基本思路：

a.將無需序列構(gòu)建成一個堆，根據(jù)升序降序需求選擇大頂堆或小頂堆;

b.將堆頂元素與末尾元素交換，將最大元素”沉”到數(shù)組末端;

c.重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整+交換步驟，直到整個序列有序。