默认的heapq是min queue实现,想知道是否有max queue的选项?谢谢。
我尝试了使用heapify-max for-max heap的解决方案,但是如何动态处理push/pop元素?似乎heapify-max只能在初始化期间使用。
import heapq
def heapsort(iterable):
h = []
for value in iterable:
heapq.heappush(h, value)
return [heapq.heappop(h) for i in range(len(h))]
if __name__ == "__main__":
print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
编辑、尝试过的heapify-max似乎不适用于动态推/弹出元素。我尝试了两种方法输出相同,两种输出都是,[0,1,2,3,4,5,6,7,8,9]。
def heapsort(iterable):
h = []
for value in iterable:
heapq.heappush(h, value)
return [heapq.heappop(h) for i in range(len(h))]
def heapsort2(iterable):
h = []
heapq._heapify_max(h)
for value in iterable:
heapq.heappush(h, value)
return [heapq.heappop(h) for i in range(len(h))]
if __name__ == "__main__":
print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print heapsort2([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
提前谢谢你, 林
在过去,我只是使用sortedcontainers的
SortedList
来实现这一点,如下所示:它不是堆,但速度快,可以直接按要求工作。
如果您绝对需要它是一个堆,您可以创建一个通用的否定类来保存您的项。
但那会占用更多的内存。
最新的cpython源中有一个_heappop_max函数,您可能会发现它很有用:
如果使用
heapq._siftdown_max
更改heappush
逻辑,则应获得所需的输出:输出:
相关问题 更多 >
编程相关推荐