算法基礎(chǔ)--堆排序

本文只是自己的筆記，并不具備過多的指導(dǎo)意義喉镰。

為了理解很多都使用了遞歸乖阵，而不是自己通過while進行壓棧處理宣赔。
代碼的初衷是便于理解，網(wǎng)上大神優(yōu)化過的代碼很多瞪浸，也不建議在項目中copy本文代碼儒将。

將數(shù)組中元素依次放入完全二叉樹中涡匀，若大于父節(jié)點則依次比對交換盯腌。保證時刻處于大根堆排序

第i個數(shù)字被插入時排序的時間復(fù)雜度與高叉樹高度相等，即O(Logi)陨瘩。
所有數(shù)字都插入依次的時間復(fù)雜度收斂于O(N)

//大根堆排序
func maximumHeapSort(arr:inout [Int]) {
    if arr.count < 2 {
        return
    }
    //大根堆排序
    for i in 0..<arr.count {
        heapInsert(arr: &arr, index: i)
    }
}

//分段大根堆排序
func heapInsert(arr:inout [Int] ,index:Int){
    
    //當前節(jié)點位置
    var currentIndex = index
    //父節(jié)點位置
    var parentIndex = (index - 1)/2
    
    //如果當前節(jié)點大于父節(jié)點腕够，則進行交換然后繼續(xù)檢查
    while arr[currentIndex] > arr[parentIndex] {
        arr.swapAt(currentIndex, parentIndex)
        currentIndex = parentIndex
        parentIndex = (currentIndex - 1)/2
    }
    
}

向下調(diào)整

在一個大根堆中级乍，某個位置的數(shù)被改變（并且變小）了帚湘。重新對堆數(shù)組進行調(diào)整

比對該位置與其左右子節(jié)點玫荣，并且與較大的一個進行交換，依次向下進行大诸。

func heapify (arr:inout Array<Int>,index:Int,heapSize:Int){
    var currentIndex = index;
    var left=2*currentIndex+1//左節(jié)點位置
    var right=left+1//右節(jié)點位置
    var largest = currentIndex //最大位置暫定為current
    while left<=heapSize {//保證左節(jié)點不越界
        
        largest = right<=heapSize && arr[right] > arr[left] ?right:left //左右節(jié)點的最大值位置(右節(jié)點越界則取左）
        
        largest = arr[largest]>arr[currentIndex] ? largest:currentIndex
        
        if largest == currentIndex {
            break //如果當前已經(jīng)為最大位置捅厂，則結(jié)束
        }
        
        arr.swapAt(currentIndex, largest)//交換當前位置與左右兩端最大位置
        
        currentIndex = largest//將當前位置下移
        left=2*currentIndex+1//左節(jié)點新位置
        right=left+1//右節(jié)點新位置
    }
}

堆排序

先構(gòu)建出一個大根堆，然后依次將頭部最大值轉(zhuǎn)移到有效數(shù)組的最后一位资柔，并且將排序區(qū)域前移焙贷。

func heapSort(arr:inout [Int]) {
    maximumHeapSort(arr:&arr)//先構(gòu)建出一個大根堆
    let size = arr.count

    for i in 0..<arr.count {
        arr.swapAt(size-1-i, 0) //將大根堆頭部最大值，移到有效數(shù)組末尾贿堰。
        heapify(arr: &arr, index: 0, heapSize: size-i-2)//將數(shù)組有效size前移盈厘，重新調(diào)整成大根堆
    }
}

其中構(gòu)建初始堆經(jīng)推導(dǎo)復(fù)雜度為O(n)，在交換并重建堆的過程中官边，需交換n-1次沸手，而重建堆的過程中，根據(jù)完全二叉樹的性質(zhì)注簿，[log2(n-1),log2(n-2)...1]逐步遞減契吉，近似為nlogn。所以堆排序時間復(fù)雜度一般認為就是O(nlogn)級诡渴。

最后

本文主要是自己的學(xué)習與總結(jié)捐晶。如果文內(nèi)存在紕漏、萬望留言斧正妄辩。如果愿意補充以及不吝賜教小弟會更加感激惑灵。

參考資料

左神牛課網(wǎng)算法課
 用數(shù)組存儲完全二叉樹時,結(jié)點的索引(數(shù)組下標)與其父子結(jié)點索引的關(guān)系.
【數(shù)據(jù)結(jié)構(gòu)】堆結(jié)構(gòu)小根堆，大根堆眼耀，插入英支，刪除等操作的實現(xiàn)
堆排序中建堆過程的時間復(fù)雜度O(n)的證明
 堆——神奇的優(yōu)先隊列(上) 【經(jīng)典】
圖解排序算法(三)之堆排序
 十大經(jīng)典排序算法（動圖演示）

算法基礎(chǔ)--堆排序

算法基礎(chǔ)--堆排序

本文只是自己的筆記，并不具備過多的指導(dǎo)意義喉镰。

目錄

堆的結(jié)構(gòu)

滿二叉樹

對于國內(nèi)的滿二叉樹

國內(nèi)的滿二叉樹屬于完全二叉樹

對于國外的滿二叉樹

完全二叉樹

數(shù)組與完全二叉樹

這個規(guī)律再芋，通常用來對通過指定下標取得相關(guān)節(jié)點下標菊霜。

大根堆&&小根堆

大根堆

小根堆

優(yōu)先級隊列用大小堆的方式更容易實現(xiàn)

對于這種最值問題，堆的調(diào)整復(fù)雜度遠低于其他結(jié)構(gòu)贺拣。

而使用大根堆的方式蓖谢，每次新入隊元素最多只需要堆整個結(jié)構(gòu)進行LogN次的調(diào)整，便可以讓堆結(jié)構(gòu)重歸有序譬涡。

用數(shù)組，建立大根堆二叉樹

向下調(diào)整

堆排序

最后

參考資料