堆指的是每個節點的值大于等于或小于等于左右節點的值的完全二叉樹結構，堆又分大頂堆(每個節點的值大于等于左右節點的值)和小頂堆(每個節點的值小于等于左右節點的值)，
使用堆進行排序的前提是要先構造一個堆出來，這里以大頂堆為例，
給定一個陣列進行構造大頂堆，
構造大頂堆的主要思路：
1、n個資料；
2、從待處理的資料里取出一個資料，插入到堆的尾部，并調整成大頂堆；
2.1、如果調整的節點值比其父節點值大，那么兩個節點交換值，重復該步驟，直到調整的節點是根節點；
2.2、否則插入節點后就是大頂堆，無需調整；
3、重復步驟2直到所有資料已取出，
構造堆的代碼實作：
堆也構建完了，那么剩下就是該怎么排序了，排序的思路是：
1、有n個元素的大根堆；
2、用根節點和當前堆的最后一個節點進行交換；
3、將剩下的n-1個元素再調整成大頂堆（調整大頂堆思路參照構造大頂堆的思路）；
4、重復步驟2、步驟3，直到完成排序，
代碼實作：
得到的陣列，逆序輸出就是排序后的陣列了，
關注公眾號 吃菜長肉
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/116936.html
標籤：其他
上一篇：Win7的IP配置網路問題
下一篇：求助，局域網內網延遲不穩定的問題