【閱讀筆記】——什么是二叉堆

big_cat 發(fā)布于2019-08-23 11:41 / 3408人閱讀

摘要：構(gòu)建二叉樹構(gòu)建二叉樹，就是把一個(gè)無序的完全二叉樹調(diào)整為二叉堆，本質(zhì)上就是讓所有非葉子節(jié)點(diǎn)一次下沉上浮構(gòu)建最大堆節(jié)點(diǎn)大的上浮，小的下沉構(gòu)建最小堆節(jié)點(diǎn)小的上浮，大的下沉文章什么是二叉堆

什么是二叉堆

二叉堆的本質(zhì)是一種完全二叉樹，它分為兩種類型：最大堆和最小堆

最大堆任何一個(gè)父節(jié)點(diǎn)的值，都大于等于它左右孩子的值，最小堆正好與之相反

二叉樹的根節(jié)點(diǎn)叫做堆頂

最大堆和最小堆的特點(diǎn)是：最大堆的堆頂是整個(gè)堆中的最大元素，最小堆的堆頂是整個(gè)堆中的最小元素

堆的自我調(diào)整

對于二叉堆有幾種操作

插入節(jié)點(diǎn)

刪除節(jié)點(diǎn)

構(gòu)建二叉堆

這幾種操作都是基于堆的自我調(diào)整

我們以最大堆為例，分析下堆的自我調(diào)整

插入節(jié)點(diǎn)

二叉堆的節(jié)點(diǎn)插入位置是完全二叉樹的最后一個(gè)位置，我們插入一個(gè)新節(jié)點(diǎn)，值為11。

這時(shí)候，我們讓節(jié)點(diǎn)11和父節(jié)點(diǎn)5作比較，如果11大于5，則交換他倆交換位置，稱為“上浮”

繼續(xù)用節(jié)點(diǎn)11和父節(jié)點(diǎn)8進(jìn)行比較，如果節(jié)點(diǎn)11大于節(jié)點(diǎn)8，則讓節(jié)點(diǎn)11繼續(xù)“上浮”

繼續(xù)比較，最終讓節(jié)點(diǎn)11上浮到堆頂位置

刪除節(jié)點(diǎn)

二叉樹刪除節(jié)點(diǎn)的過程和插入過程正好相反，它每次都是從堆頂刪除，將堆頂?shù)墓?jié)點(diǎn)與與最后一個(gè)節(jié)點(diǎn)交換位置

然后將堆頂?shù)墓?jié)點(diǎn)5和它兩個(gè)孩子進(jìn)行比較，顯然節(jié)點(diǎn)10比較打，讓他倆交換位置，稱為“下沉”

繼續(xù)讓節(jié)點(diǎn)5和它的孩子做比較，顯然大的是節(jié)點(diǎn)8，讓節(jié)點(diǎn)5繼續(xù)下沉

此時(shí)就重新構(gòu)建的二叉樹。

構(gòu)建二叉樹

構(gòu)建二叉樹，就是把一個(gè)無序的完全二叉樹調(diào)整為二叉堆，本質(zhì)上就是讓所有非葉子節(jié)點(diǎn)一次下沉（上浮）

構(gòu)建最大堆：節(jié)點(diǎn)大的上浮，小的下沉

構(gòu)建最小堆：節(jié)點(diǎn)小的上浮，大的下沉

文章：什么是二叉堆？

GPU云服務(wù)器云服務(wù)器二叉堆求二叉二叉樹二叉鏈表

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/97305.html

相關(guān)文章

算法筆記-二叉堆

摘要：二叉堆的概念二叉堆是一種特殊的二叉樹。二叉堆分為兩種最大堆和最小堆，最大堆的父節(jié)點(diǎn)一定大于其子節(jié)點(diǎn)根節(jié)點(diǎn)最大，最小堆的父節(jié)點(diǎn)小于其子節(jié)點(diǎn)根節(jié)點(diǎn)最小。這是我對二叉堆的理解，如有不對，歡迎指正，我會(huì)立即修改，謝謝。二叉堆的概念二叉堆是一種特殊的二叉樹。二叉樹是每個(gè)節(jié)點(diǎn)只有兩個(gè)子節(jié)點(diǎn)的樹（應(yīng)該都懂吧）。二叉堆分為兩種：最大堆和最小堆，最大堆的父節(jié)點(diǎn)一定大于其子...

MrZONT 2019-08-15 18:09 評論0 收藏0
Python數(shù)據(jù)結(jié)構(gòu)——二叉堆的實(shí)現(xiàn)

摘要：二叉堆的有趣之處在于，其邏輯結(jié)構(gòu)上像二叉樹，卻是用非嵌套的列表來實(shí)現(xiàn)。二叉堆結(jié)構(gòu)性質(zhì)為了更好地實(shí)現(xiàn)堆，我們采用二叉樹。圖完全二叉樹有意思的是我們用單個(gè)列表就能實(shí)現(xiàn)完全樹。下列所示的代碼是完全二叉堆的實(shí)現(xiàn)。優(yōu)先隊(duì)列的二叉堆實(shí)現(xiàn) 在前面的章節(jié)里我們學(xué)習(xí)了先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列（Queue）。隊(duì)列有一種變體叫做優(yōu)先隊(duì)列（Priority Queue）。優(yōu)先隊(duì)列的出隊(duì)（Dequ...

stackfing 2019-07-24 18:19 評論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記 - 優(yōu)先隊(duì)列、二叉堆、左式堆

摘要：模型優(yōu)先隊(duì)列是允許至少下列兩種操作的數(shù)據(jù)結(jié)構(gòu)以及找出返回并刪除優(yōu)先隊(duì)列中最小的元素。左式堆也是二叉樹，左式堆和二叉堆的唯一區(qū)別是左式堆不是理想平衡，而實(shí)際上趨向于非常不平衡。事實(shí)上，沿左式堆的右路徑是該堆中的最短路徑。 6.1 模型優(yōu)先隊(duì)列是允許至少下列兩種操作的數(shù)據(jù)結(jié)構(gòu)：insert 以及 deleteMin（找出、返回并刪除優(yōu)先隊(duì)列中最小的元素）。 insert 操作等價(jià)于 en...

SunZhaopeng 2019-08-14 14:05 評論0 收藏0
js數(shù)據(jù)結(jié)構(gòu)-二叉樹（二叉堆）

摘要：二叉樹二叉樹是一種樹形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支節(jié)點(diǎn)，一棵二叉樹通常由根節(jié)點(diǎn)，分支節(jié)點(diǎn)，葉子節(jié)點(diǎn)組成。二叉樹二叉樹(Binary Tree)是一種樹形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支節(jié)點(diǎn)，一棵二叉樹通常由根節(jié)點(diǎn)，分支節(jié)點(diǎn)，葉子節(jié)點(diǎn)組成。而每個(gè)分支節(jié)點(diǎn)也常常被稱作為一棵子樹。 showImg(https://segmentfault.com/img/bVbmEd...

ningwang 2019-08-23 14:29 評論0 收藏0
JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（十一）二叉堆

摘要：二叉堆數(shù)據(jù)結(jié)構(gòu)是一種特殊的二叉樹，他能高效快速的找出最大值和最小值，常應(yīng)用于優(yōu)先隊(duì)列和著名的堆排序算法中。二叉堆數(shù)據(jù)結(jié)構(gòu)是一種特殊的二叉樹，他能高效、快速的找出最大值和最小值，常應(yīng)用于優(yōu)先隊(duì)列和著名的堆排序算法中。二叉堆二叉堆有以下兩個(gè)特性：是一顆完全二叉樹，表示數(shù)的每一層都有左側(cè)和右側(cè)子節(jié)點(diǎn)（除最后一層的葉節(jié)點(diǎn)），并且最后一層的葉節(jié)點(diǎn)盡可能是左側(cè)子節(jié)點(diǎn) 二叉堆不是最小堆就是...

MartinHan 2019-08-26 10:58 評論0 收藏0