思路:
????????1、把無(wú)序數(shù)組構(gòu)建成最大二叉堆
????????2杀饵、循環(huán)刪除堆頂元素莽囤,移到集合尾部,調(diào)節(jié)堆產(chǎn)生新的堆頂
當(dāng)我們刪除一個(gè)最大堆的堆頂(并不是完全刪除凹髓,而是替換到最后面)烁登,經(jīng)過(guò)自我調(diào)節(jié),第二大的元素就會(huì)被交換上來(lái)蔚舀,成為最大堆的新堆頂饵沧。
正如上圖所示,當(dāng)我們刪除值為10的堆頂節(jié)點(diǎn)赌躺,經(jīng)過(guò)調(diào)節(jié)狼牺,值為9的新節(jié)點(diǎn)就會(huì)頂替上來(lái);當(dāng)我們刪除值為9的堆頂節(jié)點(diǎn)礼患,經(jīng)過(guò)調(diào)節(jié)是钥,值為8的新節(jié)點(diǎn)就會(huì)頂替上來(lái).......
由于二叉堆的這個(gè)特性,我們每一次刪除舊堆頂缅叠,調(diào)整后的新堆頂都是大小僅次于舊堆頂?shù)墓?jié)點(diǎn)悄泥。那么我們只要反復(fù)刪除堆頂,反復(fù)調(diào)節(jié)二叉堆肤粱,所得到的集合就成為了一個(gè)有序集合弹囚,
code
run