"""堆排序"""def max_heapify(heap,heapSize,root): # 調整列表中的元素并保證以root為根的堆是一個大根堆 ''' 給定某個節點的下標root，這個節點的父節點、左子節點、右子節點的下標都可以被計算出來。 父節點：(root-1)//2 左子節點：2*root + 1 右子節點：2*root + 2 即：左子節點 + 1 '''
left = 2*root + 1
right = left + 1
larger = rootif left < heapSize and heap[larger] < heap[left]:
larger = leftif right < heapSize and heap[larger] < heap[right]:
larger = rightif larger != root: # 如果做了堆調整則larger的值等于左節點或者右節點的值，這個時候做堆調整操作
heap[larger], heap[root] = heap[root], heap[larger]# 遞歸的對子樹做調整
max_heapify(heap, heapSize, larger)def build_max_heap(heap): # 構造一個堆，將堆中所有數據重新排序
heapSize = len(heap)for i in range((heapSize -2)//2,-1,-1): # 自底向上建堆
max_heapify(heap, heapSize, i)import randomdef heap_sort(heap): # 將根節點取出與最后一位做對調，對前面len-1個節點繼續進行堆調整過程。
build_max_heap(heap)# 調整后列表的第一個元素就是這個列表中最大的元素，將其與最后一個元素交換，然后將剩余的列表再遞歸的調整為最大堆for i in range(len(heap)-1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
max_heapify(heap, i, 0)# 測試if __name__ == '__main__':
a = [30, 50, 57, 77, 62, 78, 94, 80, 84]
print(a)
heap_sort(a)
print(a)
b = [random.randint(1,100) for i in range(100)]
print(b)
heap_sort(b)
print(b)

總結

以上是生活随笔為你收集整理的vector 对某个下标排序_Python实现堆排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。