使用heapq的降序

Question

我使用的是Python的heapq模块，按升序和降序排列。

对于升序，我使用的是min堆，它运行良好，如下所示：

>>> from heapq import heapify, heappop
>>> heap = [9, 3, 1, 5, 6, 2, 7]
>>> heapify(heap)
>>> heappop(heap)
1
>>> heappop(heap)
2
>>> heappop(heap)
3

对于降序，我尝试了以下不同的方法，但它们都有一些缺点：

1. 用负值作为优先项，得到反向排序。我必须使用单独的列表来使数据可重用。如果原始列表很大，那么拥有列表副本是很昂贵的。从heapq导入heapify，heappop >>>堆= 9、3、1、5、6、2、7 >>> heap_neg = -x for x in >>> heapify(heap_neg) >>> -heappop(heap_neg) 9 >>> -heappop(heap_neg) 7 >>> -heappop(heap_neg) 6
2. 使用负值元组作为优先级，这也是浪费空间。我不想将ints的列表存储为元组的列表.从heapq导入heapify，heappop >>>堆= (-9，9)，(-3，3)，(-1，1)，(-5，5)，(-6，6)，(-2,2)，(-7,7) >>>十六进制(堆)1 9 >>> heappop(堆)1 7 >>> heappop(堆)1 6。
3. 缺少使用键在heapify中排序。类似于：从heapq导入heapify，堆>>>堆= 9，3，1，5，6，2，7 >>> heapify (堆，key=lambda x:-x) #这是不工作的，因为heapify没有关键参数。
4. 如果使用，heapq._heapify_max(堆)，则必须在每个元素弹出后使用_heapify_max。喜欢：从heapq导入_heapify_max中，堆>>>堆= 9、3、1、5、6、2、7 >>> _heapify_max (堆) >>> heappop (堆)9 >>>堆(堆)#无_heapify_max的弹出结果错误结果1 >>> _heapify_max(堆) >>>堆(堆)#弹出在_heapify_max给出正确的结果7之后

是否有任何方法可以获得降序顺序，类似于如何获得升序顺序？)

Answer 1

正如我们在注释中所讨论的那样，当您使用否定的值将一个min堆翻转到一个最大堆时，您对复制数据的关注并不重要，当您从一个空堆开始并在执行过程中添加值时，这并不重要。因为这是在找到值流的运行中值时的用例，所以在添加值时忽略这些值应该是很好的。

这里有一个运行中的中间生成器，我写它只是为了再次检查它的工作方式，我的预期：

def running_median(iterable):
    left_q = [] # heap of smaller-than-median elements, stored negated
    right_q = [] # heap of larger-than-median elements

    for value in iterable:
        if len(left_q) == len(right_q): # push to left_q when they're equal size
            if len(right_q) > 0 and value > right_q[0]:
                value = heapq.heapreplace(right_q, value)
            heapq.heappush(left_q, -value)
        else: # push to right_q only when it's (strictly) smaller
            if value < -left_q[0]:
                value = -heapq.heapreplace(left_q, -value)
            heapq.heappush(right_q, value)

        # len(left_q) is always >= len(right_q) so we never yield right_q[0]
        if len(left_q) > len(right_q):
            yield -left_q[0]
        else:
            yield (-left_q[0] + right_q[0]) / 2

left_q堆存储小于或等于中值的值。每个值在被推送时都被否定，因此对其使用普通的min堆操作使其工作起来像一个最大堆。我们只需要记住重新否定我们从中获得的任何价值，才能回到原来的标志。

Answer 2

在本例中，我认为您正在寻找一个排序的链接列表，我修改了我找到的某个这里，这样它将以升序方式插入(我添加了pop函数，原因是它不在代码中，但我认为您可能需要它)：

# Python program to insert in sorted list

# Node class 
class Node:

    # Constructor to initialize the node object
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:

    # Function to initialize head
    def __init__(self):
        self.head = None

    def sortedInsert(self, new_node):

        # Special case for the empty linked list 
        if self.head is None:
            new_node.next = self.head
            self.head = new_node

        # Special case for head at end
        elif self.head.data <= new_node.data:
            new_node.next = self.head
            self.head = new_node

        else :

            # Locate the node before the point of insertion
            current = self.head
            while(current.next is not None and
                 current.next.data > new_node.data):
                current = current.next

            new_node.next = current.next
            current.next = new_node

    # Function to insert a new node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    # Utility function to prit the linked LinkedList
    def printList(self):
        temp = self.head
        while(temp):
            print(temp.data),
            temp = temp.next

    def pop(self):
        val = self.head.data
        self.head = self.head.next
        return val


# Driver program
llist = LinkedList()
new_node = Node(5)
llist.sortedInsert(new_node)
new_node = Node(10)
llist.sortedInsert(new_node)
new_node = Node(7)
llist.sortedInsert(new_node)
new_node = Node(3)
llist.sortedInsert(new_node)
new_node = Node(1)
llist.sortedInsert(new_node)
new_node = Node(9)
llist.sortedInsert(new_node)
print("Create Linked List")
llist.printList()

正如您所看到的，它只是将>=更改为<=，它完美地完成了工作

Answer 3

这方面有一些私有方法(在python3.8上进行了测试)

import heapq


if __name__ == '__main__':
    a = [1, 3, 2, 5]

    heapq._heapify_max(a)

    for item in range(0, len(a)):
        print(heapq._heappop_max(a)

结果是

sorted heap  5
sorted heap  3
sorted heap  2
sorted heap  1

但对某些人来说，使用私人方法可能不够正确。由于这个原因，我们可以通过将对象放置在修改过的包装器中来更改顺序。

class DescOrder:
    def __init__(self, entity):
        self.entity = entity

    def __lt__(self, o):
        return self.entity.__gt__(o.entity)

    def __repr__(self):
        return str(self.entity)

def check_sorting(a, b):
    new_heap = []

    for element in a:
        heapq.heappush(new_heap, DescOrder(element))

    for index in range(0, len(b)):
        assert heapq.heappop(new_heap).entity == b[index]


if __name__ == '__main__':
    check_sorting([5, 1, -1, 3, 2], [5, 3, 2, 1, -1])
    check_sorting([5, 2, -1, 3, 1], [5, 3, 2, 1, -1])
    check_sorting([-1, 2, 5, 3, 1], [5, 3, 2, 1, -1])