數(shù)據(jù)結構上機基本習題(編輯修改稿)
2025-06-18 21:27 本頁面
【文章內(nèi)容簡介】 堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆 堆排序 ? 堆 (完全二叉樹 ) 96 83 38 11 27 9 (a) 大頂堆 (max heap) 12 36 85 47 24 30 (b) 小頂堆 (min heap) 53 91 ?????? 1i2ii2ikkkk?????? 1i2ii2ikkkk{96,83,27,38,11,9} {12,36,24,85,47,30,53,91} 堆排序 ? 對一組待排序記錄的關鍵字，首先把它們按堆的定義建成小 (大 )頂堆，然后輸出堆頂?shù)淖钚?(大 )關鍵字所代表的記錄，再對剩余的關鍵字建堆，以便得到次小 (大 )的關鍵字，如此反復進行，直到全部關鍵字排成有序序列為止。 ? 實現(xiàn)堆排序需要解決兩個問題： (1) 如何建堆 ？ (2) 輸出堆頂元素后 ， 如何將剩余元素重新調(diào)整為一個新堆 ？ 堆排序過程示例 ? 下面是一個小頂堆，輸出堆頂元素后（即將序列末端元素與堆頂元素交換），將剩余元素重新調(diào)整為一個新堆的方法是：從樹根開始，若以某結點為根的子樹不是堆，則將其孩子中的較小者與之交換，即將非堆的子樹推向葉子方向 12 36 85 47 24 30 53 91 91 36 85 47 24 30 53 12 交換堆頂元素與序列末端的元素 比較 比較 交換 return 堆排序過程示例 (續(xù) ) ? 輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆的方法是：從樹根開始，若以某結點為根的子樹不是堆，則將其孩子中的較小者與之交換，即將非堆的子樹推向葉子方向 24 36 85 47 30 91 53 12 繼續(xù)向葉子方向調(diào)整 24 36 85 47 91 30 53 12 比較 比較 交換 堆排序過程示例 (續(xù) ) ? 一旦已調(diào)整為堆，則輸出堆頂元素，重復將剩余元素重新調(diào)整為一個新堆。 24 36 85 47 30 91 53 12 53 36 85 47 30 91 24 12 交換堆頂元素與序列末端的元素 堆排序過程示例 (續(xù) ) ? 輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆 30 36 85 47 53 91 24 12 調(diào)整成堆 53 36 85 47 30 91 24 12 ? 繼續(xù)此過程，就可以將元素按照需要的順序排列 ? 要使得數(shù)組中元素最后從小到大排列，則宜采用大頂堆 堆排序過程分析 ? 輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆 91 36 85 47 53 30 24 12 反復將堆頂元素與序列末端的元素的交換，并重新調(diào)整成堆。 91 85 47 36 53 30 24 12 ?調(diào)整堆元素 (篩選 ) 對于給出的關鍵字序列 ， 經(jīng)初始建堆后便得到小 (大 )頂堆 ， 從而得到最小 (大 )關鍵字 。 在輸出堆頂元素之后 ， 用堆中最后一個元素替代之 。 此時由于以 K2和 K3為根的 子樹仍具有堆的特性 ，因此只需自上而下進行調(diào)整即可 。 調(diào)整過程為： 首先令 K1的兩個子樹根進行比較 ， 令其中較小 (大 )者與 K1相比較 ， 將最小 (大 )元素交換至 K1， 使得 K K2和 K3成為堆 。 由于 交換后破壞了子樹的堆性質 ， 則需再次進行與上述過程類似的調(diào)整 ， 直至進行到最下層的葉結點為止 。調(diào)整后即得到一個有 n1個元素的新堆 ， 從而得到次小關鍵字 。 堆排序過程分析 (續(xù) ) ? 輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆 ?調(diào)整堆元素 (篩選 ) 對于給出的關鍵字序列 ， 經(jīng)初始建堆后便得到小 (大 )頂堆 ， 從而得到最小 (大 )關鍵字 。 在輸出堆頂元素之后 ， 用堆中最后一個元素替代之 。 此時由于以 K2和K3為根的子樹仍具有堆的特性 ， 因此只需自上而下進行調(diào)整即可 。 首先令 K1將的兩個子樹根進行比較 ， 令其中較小 (大 )者與 K1相比較 ，將最小 (大 )元素交換至 K1， 使得 K K2和 K3成為堆 。 由于交換后破壞了右子樹的堆 ， 則需再次進行與上述類似的調(diào)整 ， 直至進行到最下層的葉結點 。調(diào)整后即得到一個有 n1個元素的新堆 ， 從而得到次小關鍵字 。 重復上述過程 ， 將堆頂元素與堆中最后一個元素交換且調(diào)整 ，又得到了有 n2個元素的新堆 。 為節(jié)省存貯開銷 ， 可以把輸出的最小 (大 )關鍵字放在 Kn的位置上 ， 把第二次輸出的次小 (大 )關鍵字存放在 Kn1的位置上 …… ， 直至最大 (小 )關鍵字放在 K1的位置上 。 如此，我們已經(jīng)可以在初始情況為堆的情況下完成排序，那么， 如何建立起初始堆呢？ 建初始小頂堆 47 36 91 12 53 30 24 85 12 36 85 47 24 30 53 91 ? 元素序列為： 47,36,53,91,12,30,24,85 建立小頂堆 建初始堆 47 36 91 12 53
研究報告相關推薦
鄂ICP備17016276號-1