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


当前回答

最简单的方法是反转键的值并使用heapq。例如,将1000.0转换为-1000.0,将5.0转换为-5.0。

其他回答

最简单最理想的解决方案

将这些值乘以-1

好了。所有最高的数字现在都是最低的,反之亦然。

只要记住,当您弹出一个元素与-1相乘以再次获得原始值时。

python中有内置堆,但我只是想分享一下,如果有人像我一样想自己构建它。 我是python的新手,不要判断我是否犯了错误。 算法是有效的,但效率我不知道

class Heap :

    def __init__(self):
        self.heap = []
        self.size = 0


    def add(self, heap):
        self.heap = heap
        self.size = len(self.heap)

    def heappush(self, value):
        self.heap.append(value)
        self.size += 1


    def heapify(self, heap ,index=0):

        mid = int(self.size /2)
        """
            if you want to travel great value from bottom to the top you need to repeat swaping by the hight of the tree
            I  don't how how can i get the  height of the tree that's why i use sezi/2
            you can find height by this formula
            2^(x) = size+1  why 2^x because tree is growing exponentially 
            xln(2) = ln(size+1)
            x = ln(size+1)/ln(2)
        """

        for i in range(mid):
            self.createTee(heap ,index)

        return heap

    def createTee(self,  heap ,shiftindex):

        """
        """
        """

            this pos reffer to the index of the parent only parent with children
                    (1)
                (2)      (3)           here the size of list is 7/2 = 3
            (4)   (5)  (6)  (7)        the number of parent is 3 but we use {2,1,0} in while loop
                                       that why a put pos -1

        """
        pos = int(self.size /2 ) -1
        """
            this if you wanna sort this heap list we should swap max value in the root of the tree with the last
            value in the list and if you wanna repeat this until sort all list you will need to prevent the func from
            change what we already sorted I should decrease the size of the list that will heapify on it

        """

        newsize = self.size - shiftindex
        while pos >= 0 :
            left_child = pos * 2 + 1
            right_child = pos * 2 + 2
            # this mean that left child is exist
            if left_child < newsize:
                if right_child < newsize:
                    # if the right child exit we wanna check if left child > rightchild
                    # if right child doesn't exist we can check that we will get error out of range
                    if heap[pos] < heap[left_child] and heap[left_child]  > heap[right_child] :
                        heap[left_child] , heap[pos] = heap[pos], heap[left_child]
                # here if the righ child doesn't exist
                else:
                    if heap[pos] < heap[left_child] :
                        heap[left_child] , heap[pos] = heap[pos], heap[left_child]
            # if the right child exist
            if right_child < newsize :
                if heap[pos] < heap[right_child] :
                    heap[right_child], heap[pos] = heap[pos], heap[right_child]
            pos -= 1

        return heap

    def sort(self ):
        k = 1
        for i in range(self.size -1 ,0 ,-1):
            """
            because this is max heap we swap root with last element in the list

            """
            self.heap [0] , self.heap[i] = self.heap[i], self.heap[0]
            self.heapify(self.heap ,k)
            k+=1

        return self.heap


h = Heap()
h.add([5,7,0,8,9,10,20,30,50,-1] )
h.heappush(-2)
print(" before heapify ")
print(h.heap)
print(" after heapify ")
print(h.heapify(h.heap,0))
print(" after sort ")
print(h.sort())

输出:

之前heapify [5,7,0,8,9,10,20,30,50, -1, -2]

heapify后 [50, 30, 20, 8, 9, 10, 0, 7, 5, -1, -2]

排序后 [-2, -1, 0,5,7,8,9,10,20,30,50]

希望您能理解我的代码。如果有什么你不明白的地方,请发表评论,我会尽力帮助你

heapq模块拥有实现maxheap所需的一切。 它只做max-heap的堆推功能。 我已在下面示范如何克服这一点

在heapq模块中添加这个函数:

def _heappush_max(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown_max(heap, 0, len(heap)-1)

最后加上这句话:

try:
    from _heapq import _heappush_max
except ImportError:
    pass

瞧!这是完成了。

PS -转到heapq函数。首先在编辑器中写入“import heapq”,然后右键单击“heapq”并选择转到定义。

扩展int类并重写__lt__是一种方法。

import queue
class MyInt(int):
    def __lt__(self, other):
        return self > other

def main():
    q = queue.PriorityQueue()
    q.put(MyInt(10))
    q.put(MyInt(5))
    q.put(MyInt(1))
    while not q.empty():
        print (q.get())


if __name__ == "__main__":
    main()

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