国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機(jī)構(gòu)

手機(jī)站
千鋒教育

千鋒學(xué)習(xí)站 | 隨時(shí)隨地免費(fèi)學(xué)

千鋒教育

掃一掃進(jìn)入千鋒手機(jī)站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習(xí)站小程序
隨時(shí)隨地免費(fèi)學(xué)習(xí)課程

當(dāng)前位置:首頁(yè)  >  技術(shù)干貨  > 堆和樹有什么區(qū)別?

堆和樹有什么區(qū)別?

來源:千鋒教育
發(fā)布人:xqq
時(shí)間: 2023-10-11 03:06:20 1696964780

一、堆和樹的區(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è)序列有序。

聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強(qiáng)師集結(jié),手把手帶你蛻變精英
請(qǐng)您保持通訊暢通,專屬學(xué)習(xí)老師24小時(shí)內(nèi)將與您1V1溝通
免費(fèi)領(lǐng)取
今日已有369人領(lǐng)取成功
劉同學(xué) 138****2860 剛剛成功領(lǐng)取
王同學(xué) 131****2015 剛剛成功領(lǐng)取
張同學(xué) 133****4652 剛剛成功領(lǐng)取
李同學(xué) 135****8607 剛剛成功領(lǐng)取
楊同學(xué) 132****5667 剛剛成功領(lǐng)取
岳同學(xué) 134****6652 剛剛成功領(lǐng)取
梁同學(xué) 157****2950 剛剛成功領(lǐng)取
劉同學(xué) 189****1015 剛剛成功領(lǐng)取
張同學(xué) 155****4678 剛剛成功領(lǐng)取
鄒同學(xué) 139****2907 剛剛成功領(lǐng)取
董同學(xué) 138****2867 剛剛成功領(lǐng)取
周同學(xué) 136****3602 剛剛成功領(lǐng)取
相關(guān)推薦HOT
哈希樹hashtree常應(yīng)用在哪些現(xiàn)實(shí)場(chǎng)景?

一、哈希樹hashtree常應(yīng)用現(xiàn)實(shí)場(chǎng)景1、場(chǎng)景一:安全加密日常用戶密碼加密通常使用的都是 md5、sha等哈希函數(shù),因?yàn)椴豢赡妫椅⑿〉膮^(qū)別加密之...詳情>>

2023-10-11 04:55:54
數(shù)據(jù)結(jié)構(gòu)sqlist和seqlist有什么區(qū)別?

一、數(shù)據(jù)結(jié)構(gòu)sqlist和seqlist的區(qū)別sqlist是函數(shù)的名稱,seqlist是一種類型,動(dòng)態(tài)分配數(shù)組順序表的類型。sqlist為靜態(tài)分配#define MaxSize 50?...詳情>>

2023-10-11 04:42:55
Int main和void main有什么區(qū)別?

一、Int main和void main有什么區(qū)別1、有無返回值void main沒有返回值,int main有返回值。2、返回值類型int main返回int類型的數(shù)據(jù),void main...詳情>>

2023-10-11 04:36:26
hash中的Key和value有什么區(qū)別?

一、hash中的Key和value的區(qū)別hash中的Key和value本意是鑰匙和值的意思,在應(yīng)用中通常被用作鍵值對(duì),例如在map、json中等。在鍵值對(duì)中,key是關(guān)...詳情>>

2023-10-11 04:34:49
數(shù)據(jù)結(jié)構(gòu)到底是什么?

一、數(shù)據(jù)結(jié)構(gòu)到底是什么數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包括三方面的內(nèi)容:邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)...詳情>>

2023-10-11 04:07:19
快速通道