【從堆的定義到優(yōu)先隊(duì)列、堆排序】 10分鐘看懂必考的數(shù)據(jù)結(jié)構(gòu)——堆
2023-07-09 20:58 作者:Ssssssssssf | 我要投稿
# 堆： 了解下就好 # 一、堆是完全二叉樹的結(jié)構(gòu) # 什么是完全二叉樹：1.只允許最后一行不滿 2.最后一行必須從左往右排，中間不能有間隔 # 二、堆序性 1.小根堆，父節(jié)點(diǎn)都要更小 2.大根堆，父節(jié)點(diǎn)都要更大 # 三、堆的存儲(chǔ)，因?yàn)槭峭耆鏄?，所以可以根?jù)層序遍歷，來得到一個(gè)數(shù)組，此時(shí)，父節(jié)點(diǎn)為i時(shí)，左右子節(jié)點(diǎn)一定為2i+1/2 # 四、堆有兩個(gè)基本操作：1.上濾，通常用于插入新元素到根中時(shí)，向上調(diào)整位置時(shí) # 2.下濾（因?yàn)楸仨氁獫M足堆序性的話，所以對(duì)不滿足的要操作），把根節(jié)點(diǎn)向下調(diào)整的操作叫下濾 # 五、自頂向下建堆法：1.插入堆 2.上濾 # 六、自下而上建堆法：對(duì)每個(gè)父節(jié)點(diǎn)進(jìn)行下濾（從最下面的父節(jié)點(diǎn)開始）-- 復(fù)雜度O(N) # 七、應(yīng)用 1.優(yōu)先隊(duì)列：彈出最小元素 -- 可以用來實(shí)現(xiàn)堆排序，用大根堆排序完，彈出的是正序，小根堆反 2.插入：就是上濾
標(biāo)簽：
