python堆排序的库_heapy()：python自帶的堆排序

堆是一個二叉樹&＃xff0c;其中每個父節點的值都小於或等於其所有子節點的值。整個堆的最小元素總是位於二叉樹的根節點。python的heapq模塊提供了對堆的支持。 堆數據結構最重要的特征是heap[0]永遠是最小的元素

1. heap為定義堆&＃xff0c;item增加的元素

heapq.heappush(heap,item)

>>> import heapq

>>> h &＃61; []

>>> heapq.heappush(h,2)

>>> h

[2]

2. 將列表轉換為堆

heapq.heapify(list)

>>> list &＃61; [1,2,3,5,1,5,8,9,6]

>>> heapq.heapify(list)

>>> list

[1, 1, 3, 5, 2, 5, 8, 9, 6]

3. 刪除最小值&＃xff0c;因為堆的特征是heap[0]永遠是最小的元素&＃xff0c;所以一般都是刪除第一個元素

heapq.heappop(heap)

>>> list

[1, 1, 3, 5, 2, 5, 8, 9, 6]

>>> heapq.heappop(list)

1

>>> list

[1, 2, 3, 5, 6, 5, 8, 9]

4. 刪除最小元素值&＃xff0c;添加新的元素值

heapq.heapreplace(heap.item)

>>> list

[1, 2, 3, 5, 6, 5, 8, 9]

>>> heapq.heapreplace(list,99)

1

>>> list

[2, 5, 3, 9, 6, 5, 8, 99]

5. 首先判斷添加元素值與堆的第一個元素值對比&＃xff0c;如果大&＃xff0c;則刪除第一個元素&＃xff0c;然后添加新的元素值&＃xff0c;否則不更改堆

heapq.heapreplace(heap,item)

>>> list

[2, 5, 3, 9, 6, 5, 8, 99]

>>> heapq.heappushpop(list,6)

2

>>> list

[3, 5, 5, 9, 6, 6, 8, 99]

>>> heapq.heappushpop(list,1)

1

>>> list

[3, 5, 5, 9, 6, 6, 8, 99]

6. 將多個堆合並

heapq.merge(…)

>>> list

[3, 5, 5, 9, 6, 6, 8, 99]

>>> h

[1000]

>>> for i in heapq.merge(h,list):

... print(i,end&＃61;" ")

...

3 5 5 9 6 6 8 99 1000

7. 查詢堆中的最大元素&＃xff0c;n表示查詢元素個數

heapq.nlargest(n,heap)

>>> list

[3, 5, 5, 9, 6, 6, 8, 99]

>>> heapq.nlargest(3,list)

[99, 9, 8]

>>>

8. 查詢堆中的最小元素&＃xff0c;n表示查詢元素的個數

heapq.nsmallest(n,heap)

>>> list

[3, 5, 5, 9, 6, 6, 8, 99]

>>> heapq.nsmallest(3,list)

[3, 5, 5]

9. 用heapy建立大頂堆&＃xff1a;將數據以相反數的形式存入堆&＃xff0c;再以相反數的形式取出

push(e) --->>> push(-e)

pop(e) --->>> pop(-e)

參考文獻&＃xff1a;