Python包含了用于min-堆的heapq模块,但我需要一个max堆。在Python中我应该使用什么来实现最大堆?


当前回答

如果插入的键具有可比性但不像int型,则可能重写它们上的比较操作符(即<=变成>,>变成<=)。否则,您可以重写heapq。heapq模块中的_siftup(最后都是Python代码)。

其他回答

如果插入的键具有可比性但不像int型,则可能重写它们上的比较操作符(即<=变成>,>变成<=)。否则,您可以重写heapq。heapq模块中的_siftup(最后都是Python代码)。

你可以使用

import heapq
listForTree = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]    
heapq.heapify(listForTree)             # for a min heap
heapq._heapify_max(listForTree)        # for a maxheap!!

如果你想要弹出元素,使用:

heapq.heappop(minheap)      # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap

最好的方法:

from heapq import *
h = [5, 7, 9, 1, 3]
h_neg = [-i for i in h]
heapify(h_neg)            # heapify
heappush(h_neg, -2)       # push
print(-heappop(h_neg))    # pop
# 9

允许您选择任意数量的最大或最小的项目

import heapq
heap = [23, 7, -4, 18, 23, 42, 37, 2, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
heapq.heapify(heap)
print(heapq.nlargest(3, heap))  # [42, 42, 37]
print(heapq.nsmallest(3, heap)) # [-4, -4, 2]
arr = [3,4,5,1,2,3,0,7,8,90,67,31,2,5,567]
# max-heap sort will lead the array to assending order
def maxheap(arr,p):
    
    for i in range(len(arr)-p):
        if i > 0:
            child = i
            parent = (i+1)//2 - 1
            
            while arr[child]> arr[parent] and child !=0:
                arr[child], arr[parent] = arr[parent], arr[child]
                child = parent
                parent = (parent+1)//2 -1
                
    
def heapsort(arr):
    for i in range(len(arr)):
        maxheap(arr,i)
        arr[0], arr[len(arr)-i-1]=arr[len(arr)-i-1],arr[0]
        
    return arr
        

print(heapsort(arr))

试试这个