一、堆和樹的區(qū)別
1、節(jié)點(diǎn)的順序
在二叉搜索樹中,左子節(jié)點(diǎn)必須比父節(jié)點(diǎn)小,右子節(jié)點(diǎn)必須必比父節(jié)點(diǎn)大。但是在堆中并非如此。在最大堆中兩個(gè)子節(jié)點(diǎn)都必須比父節(jié)點(diǎn)小,而在最小堆中,它們都必須比父節(jié)點(diǎn)大。
2、內(nèi)存占用
普通樹占用的內(nèi)存空間比它們存儲(chǔ)的數(shù)據(jù)要多。你必須為節(jié)點(diǎn)對(duì)象以及左/右子節(jié)點(diǎn)指針分配額外內(nèi)存。堆僅僅使用一個(gè)數(shù)據(jù)來存儲(chǔ)數(shù)組,且不使用指針。
3、平衡
二叉搜索樹必須是“平衡”的情況下,其大部分操作的復(fù)雜度才能達(dá)到O(log n)。你可以按任意順序位置插入/刪除數(shù)據(jù),或者使用 AVL 樹或者紅黑樹,但是在堆中實(shí)際上不需要整棵樹都是有序的。我們只需要滿足對(duì)屬性即可,所以在堆中平衡不是問題。因?yàn)槎阎袛?shù)據(jù)的組織方式可以保證O(log n) 的性能。
4、搜索
在二叉樹中搜索會(huì)很快,但是在堆中搜索會(huì)很慢。在堆中搜索不是名列前茅優(yōu)先級(jí),因?yàn)槭褂枚训哪康氖菍⒆畲螅ɑ蛘咦钚。┑墓?jié)點(diǎn)放在最前面,從而快速的進(jìn)行相關(guān)插入、刪除操作。
延伸閱讀:
二、堆排序(Heap Sort)
堆排序的基本思想是:將待排序序列構(gòu)造成一個(gè)大頂堆,此時(shí),整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換,此時(shí)末尾就為最大值。然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)堆,這樣會(huì)得到n個(gè)元素的次大值。如此反復(fù)執(zhí)行,便能得到一個(gè)有序序列了。
1.構(gòu)造初始堆。將給定無序序列構(gòu)造成一個(gè)大頂堆(一般升序采用大頂堆,降序采用小頂堆)。
看堆頂?shù)男蛱?hào),來判斷名列前茅個(gè)非葉子節(jié)點(diǎn)的索引。這點(diǎn)很重要!
2.此時(shí)我們從最后一個(gè)非葉子結(jié)點(diǎn)開始,從左至右,從下至上進(jìn)行調(diào)整。
調(diào)整就是找每個(gè)非葉子節(jié)點(diǎn)的葉子節(jié)點(diǎn)是不是比他大,把大的交換上來,這一層交換結(jié)束再交換上一層,直到使根節(jié)點(diǎn)即堆頂元素為最大值。
這里要注意,如果上一層交換之后,當(dāng)前層又不滿足堆的要求,繼續(xù)交換。
3. 將堆頂元素與末尾元素進(jìn)行交換,使末尾元素最大。然后繼續(xù)調(diào)整堆,再將堆頂元素與末尾元素交換,得到第二大元素。如此反復(fù)進(jìn)行交換、重建、交換。
也就是說每一層堆頂與末尾交換,都能得到一個(gè)當(dāng)前的最大值,放在有序數(shù)組的最后面相當(dāng)于!然后從后往前填充為有序數(shù)組。
再簡(jiǎn)單總結(jié)下堆排序的基本思路:
a.將無需序列構(gòu)建成一個(gè)堆,根據(jù)升序降序需求選擇大頂堆或小頂堆;
b.將堆頂元素與末尾元素交換,將最大元素”沉”到數(shù)組末端;
c.重新調(diào)整結(jié)構(gòu),使其滿足堆定義,然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素,反復(fù)執(zhí)行調(diào)整+交換步驟,直到整個(gè)序列有序。