成人亚洲一区,青青在线精品播放,国产唐伯虎麻豆

從二叉搜索樹和平衡二叉樹的介紹中，可以發(fā)現(xiàn)二叉樹這種結(jié)構(gòu)具有一個很好的特性，當(dāng)有序的二叉樹構(gòu)造完成之后，更改樹中節(jié)點后，只需要 $O(log_2N)$ 的時間復(fù)雜度即可將二叉樹重新調(diào)整為有序狀態(tài)。若構(gòu)造出一種具有特殊節(jié)點順序的二叉樹，使得每次對二叉樹執(zhí)行插入或刪除節(jié)點操作后，都調(diào)整保持二叉樹根節(jié)點的值為樹中節(jié)點的極值，則 $N$ 個元素的集合，構(gòu)造出這種二叉樹后，只需要對樹執(zhí)行 $N-1$ 次的取根節(jié)點操作，即可獲得一個有序序列。整個取節(jié)點加調(diào)整操作的時間復(fù)雜度為 $O(Nlog_2N)$ ，若構(gòu)造這種二叉樹的時間復(fù)雜度不高于 $O(Nlog_2N)$ ，則采用構(gòu)造這種二叉樹的方式來完成排序的時間復(fù)雜度為 $O(Nlog_2N)$ 。

堆定義

上面提到的利用具有特殊節(jié)點順序的二叉樹完成排序的方式，就是堆排序。這里所說的節(jié)點順序是指：樹中每個節(jié)點的值都不小于（不大于）它的子節(jié)點值。堆描述的是一顆完全二叉樹，在對數(shù)組進行排序的過程中，并不是真的構(gòu)建一個二叉樹結(jié)構(gòu)，只是將數(shù)組中元素下標映射到完全二叉樹，利用元素下標來表示父節(jié)點和子節(jié)點關(guān)系。

list type

tree type

通過以上兩張圖可知，堆中父子節(jié)點的下標關(guān)系為：

下標為 $i$ 的節(jié)點，其左子節(jié)點下標為 $2*i+1$
下標為 $i$ 的節(jié)點，其右子節(jié)點下標為 $2*i+2$
下標為 $i$ 的節(jié)點，其父節(jié)點下標為 $\lfloor {\frac {i-1} 2} \rfloor(i\ge1)$

算法過程

以遞增排序為例，集合初始為待排序集合，已排序集合為空

構(gòu)造最大堆，即調(diào)整待排序集合，使得元素映射出的完全二叉樹，滿足每個節(jié)點元素值都不小于其子節(jié)點值
替換待排序集合中第一個元素和最后一個元素值，即在待排序集合映射出的完全二叉樹上，將根節(jié)點值和樹中最下面一層、最右邊的節(jié)點值進行替換
調(diào)整堆結(jié)構(gòu)使其滿足節(jié)點大小順序，標記待排序集合最后一個元素為已排序
重復(fù)步驟2, 3，直到待排序集合只有一個元素

演示示例

調(diào)整為最大堆結(jié)構(gòu)

要保證每個節(jié)點的值不小于其左右子節(jié)點的值，只需要從后往前遍歷集合中每個具有子節(jié)點的節(jié)點，使得其節(jié)點值不小于左右子節(jié)點的值即可（遞歸與子節(jié)點進行比較）。已知下標為 $i$ 的節(jié)點，其父節(jié)點下標為 $\lfloor {\frac {i-1} 2} \rfloor(i\ge1)$ ，所以具有 $N$ 個元素的集合，起始遍歷節(jié)點的下標為 $\lfloor { {\frac {N} 2} -1} \rfloor(i\ge1)$ 。

起始待調(diào)整元素下標為 4，即值為 2 的節(jié)點

1 次調(diào)整后，下一個待調(diào)整元素下標為 3，即值為 0 的節(jié)點

2 次調(diào)整后，下一個待調(diào)整元素下標為 2，即值為 4 的節(jié)點

3 次調(diào)整后，下一個待調(diào)整元素下標為 1，即值為 3 的節(jié)點。這里注意，節(jié)點 3 與子節(jié)點 9 比較并交換后，需要遞歸與子節(jié)點進行比較，直到值不小于子節(jié)點值

step_1

step_2

4 次調(diào)整后，下一個待調(diào)整元素下標為 0，即值為 5 的節(jié)點。同樣涉及遞歸操作

5 次調(diào)整后，當(dāng)前結(jié)構(gòu)即為最大堆

調(diào)整代碼

def transformToHeap(arr, index, end):
    targetIndex, leftChildIndex, rightChildIndex = index, 2 * index + 1, 2 * index + 2
    if leftChildIndex < end and arr[leftChildIndex] > arr[targetIndex]:
        targetIndex = leftChildIndex
    if rightChildIndex < end and arr[rightChildIndex] > arr[targetIndex]:
        targetIndex = rightChildIndex
    if not targetIndex == index:
        arr[index], arr[targetIndex] = arr[targetIndex], arr[index]
        transformToHeap(arr, targetIndex, end)

代碼中聲明 $targetIndex$ 用于指向根節(jié)點、左右子節(jié)點中的最大節(jié)點，若需要替換節(jié)點值，則遞歸調(diào)整替換后的根節(jié)點和其左右子節(jié)點。 $end$ 變量用于標志待排序集合的邊界。

迭代獲取堆頂元素

重復(fù)將待排序集合首元素和尾元素進行替換，標記替換后的尾元素為已排序，并調(diào)整堆結(jié)構(gòu)使其重新成為最大堆。

起始待替換根節(jié)點為 9，第 1 次替換并調(diào)整后結(jié)構(gòu)后（調(diào)整過程上面已列出）
待排序集合：[8, 7, 4, 6, 5, 1, 2, 3, 0]
已排序集合：[9]

下一個待替換根節(jié)點為 8，第 2 次替換并調(diào)整后結(jié)構(gòu)后
待排序集合：[7, 6, 4, 3, 5, 1, 2, 0]
已排序集合：[8, 9]

...
...
...

下一個待替換根節(jié)點為 0，第 9 次替換并調(diào)整后結(jié)構(gòu)后
待排序集合：[0]
已排序集合：[1, 2, 3, 4, 5, 6, 7, 8, 9]

觀察以上過程可知，每次排序后待排序集合元素數(shù)減一。 $N$ 個元素的序列，經(jīng)過 $N-1$ 次排序后，待排序集合元素數(shù)為一，即完成排序。

迭代操作代碼

def heapSort(arr):
    index = len(arr) // 2 - 1
    while index >= 0:
        transformToHeap(arr, index, len(arr))  # transform arr to heap arr
        index = index - 1
    num = 1
    while num < len(arr):
        arr[0], arr[-num] = arr[-num], arr[0]
        transformToHeap(arr, 0, len(arr) - num)  # transform arr to heap arr
        num = num + 1

代碼中第一個循環(huán)為構(gòu)造最大堆，第二個循環(huán)為替換待排序集合首尾元素，并調(diào)整最大堆。

算法分析

堆排序是一種不穩(wěn)定排序算法，對于 $N$ 個元素的序列，構(gòu)造堆過程，需要遍歷的元素次數(shù)為 $O(N)$ ，每個元素的調(diào)整次數(shù)為 $O(log_2N)$ ，所以構(gòu)造堆復(fù)雜度為 $O(Nlog_2N)$ 。迭代替換待排序集合首尾元素的次數(shù)為 $O(N)$ ，每次替換后調(diào)整次數(shù)為 $O(log_2N)$ ，所以迭代操作的復(fù)雜度為 $O(Nlog_2N)$ 。由此可知堆排序的時間復(fù)雜度為 $O(Nlog_2N)$ ，排序過程屬于原地排序，不需要額外的存儲空間，所以空間復(fù)雜度為 $O(1)$ 。

github 鏈接：堆排序

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

排序算法（五）：堆排序

排序算法（五）：堆排序

堆定義

算法過程