22計算機考研數(shù)據(jù)結(jié)構(gòu)：堆排序

　　計算機的競爭度逐年加大，報考學生越來越多，對于打算報考2022考研計算機的考生們來說復(fù)習是難點。下面小編整理了2022考研計算機數(shù)據(jù)結(jié)構(gòu)：堆排序，一起來看看吧。

　　堆排序

　　大根堆的定義：完全二叉樹，任一非葉子結(jié)點都大于等于它的孩子，也就是說根結(jié)點是最大的。而且顯然大根堆的任一棵子樹也是大根堆。

　　堆排序的基本思想：記錄區(qū)的分為無序區(qū)和有序區(qū)前后兩部分用無序區(qū)的數(shù)建大根堆，得到的根(最大的數(shù))和無序區(qū)的最后一個數(shù)交換，也就是將該根歸入有序區(qū)的最前端如此重復(fù)下去，直至有序區(qū)擴展至整個記錄區(qū)。

　　具體操作可按下面步驟實現(xiàn)：

　　1.建大根堆

　　2.交換根和無序區(qū)最后一個數(shù)

　　3.重建大根堆，因為交換只是使根改變了，所以左右子樹依然分別是大根堆。

　　4.比較根，左子樹的根和右子樹的根，如果根最大，則無須再作調(diào)整，樹已經(jīng)是大根堆了如果左子樹的根最大，交換它與根，再遞歸調(diào)整左子樹如果右子樹的根最大，交換它與根，再遞歸調(diào)整右子數(shù)。

　　5.遞歸調(diào)整到葉子的時候，樹就是大根堆了。

　　(注：本文來自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系刪除)