一、內置模塊

在python中，堆排序已經設置好了內置模塊，不想自己寫的話可以使用內置模塊，真的很方便，但是堆排序算法的底層邏輯最好還是要了解并掌握一下的。

使用heapq模塊的heapify()函數將列表轉換為堆，然后使用heappop()和heappush()函數執行堆排序操作。

代碼實現

import heapq  # 導入包
import random   # 隨機數庫，生成隨機數li = list(range(100))
random.shuffle(li)print(li)
heapq.heapify(li)   # 建堆的過程# 使用內置模塊實現堆排序
n = len(li)
for i in range(n):print(heapq.heappop(li), end=",")

二、topk問題?

問題描述：現在有n個數，設計算法得到前k個大的數。（k<n）

解決思路：

? ? ? ? 取列表前k個元素建立一個小根堆。堆頂就是目前第k大的數。

? ? ? ? 依次向后遍歷原列表，對于列表中的元素，如果小于堆頂，則忽略該元素；如果大于堆頂，則將堆頂更換為該元素，并且對堆頂進行一次調整。

? ? ? ? 遍歷列表所有元素后，倒序彈出堆頂。

代碼實現：

def sift(li, low, high):""":param li: 用列表存放樹結構:param low: 堆的根節點位置:param high: 堆的最后一個元素的位置:return:"""i = low   # i最開始指向根節點j = 2 * i + 1   # j最開始指向左孩子tmp = li[low]   # 將棧頂保存起來while j <= high:  # 循環條件為只要j不越過列表的界if j + 1 <= high and li[j+1] < li[j]:  j = j+1    # 那么把指針指向數字大的右孩子if li[j] < tmp:li[i] = li[j]   # 將i位置賦值為較大的數i = j   # 并將i，j指針向下移動j = 2 * i +1else:  # 如果tmp更大，將tmp放到i的位置上li[i] = tmp   # 把tmp放到某個子樹的根節點上breakelse:li[i] = tmp   # 把tmp放到葉子節點上def topk(li, k):heap = li[0:k]# 1.建堆for i in range((k-2)//2, -1, -1):sift(heap, i, k-1)# 2.遍歷并向下調整for i in range(k, len(li)-1):if li[i] > heap[0]:heap[0] = li[i]   #sift(heap, 0, k-1)# 3.出數for i in range(k-1,-1, -1):heap[0], heap[i] = heap[i], heap[0]sift(heap, 0, i-1)return heap# 測試例子
import random
li = list(range(1000))
random.shuffle(li)
print(topk(li, 10))

運行結果

三、學習碎碎念?

三天！我終于把這個堆排序看完了！只是看完了，還沒有真正的理解會運用。三月的第一天，新的一個月繼續加油！每天的課老多，還要抽出空來自己學習，真的是超級累啊，慢慢來吧，總會熬過去的！

? ??