Descending order using heapq

Question

I am using heapq module of Python get data in ascending and descending order.

For ascending, I am using min heap and it works well as follow:

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

For descending, I have tried following different approaches but all of them have some drawback:

1. Using negative value as the priorirty to get reverse sort. I have to use separate list to make data reusable. If the original list is big, having copy of list is costly.

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

2. Using tuple with negative value as priority, this is also waste of space. I would not like to store list of ints as list of tuples.

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

3. Using key to sort in heapify is missing. Something like:

   >>> from heapq import heapify, heappop
   >>> heap = [9, 3, 1, 5, 6, 2, 7]
   >>> heapify(heap, key=lambda x:-x) # This doesn't work as heapify don't have key parameter
   

4. If I use, heapq._heapify_max(heap), I will have to _heapify_max after each element pop. Like:

   >>> from heapq import _heapify_max, heappop
   >>> heap = [9, 3, 1, 5, 6, 2, 7]
   >>> _heapify_max(heap)
   >>> heappop(heap)
   9
   >>> heappop(heap)  # popping without _heapify_max gives wrong result
   1
   >>> _heapify_max(heap)
   >>> heappop(heap) # popping after _heapify_max gives correct result
   7
   

Is there any way I can get descending order similar to how I got ascending order? :)

Answer 1

As we discussed in the comments, your concerns about copying data when using negated values to flip a min-heap into a max-heap don't matter when you're starting with an empty heap and adding the values as you go. Since that's the use case when finding the running median of a stream of values, negating the values as you add them should work just fine.

Here's a running median generator I wrote just to double check that it works the way I expected:

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

The left_q heap stores the less-than-or-equal-to-median values. Each value is negated when it's pushed, so using the normal min-heap operations on it makes it work like a max-heap. We just need to remember to re-negate any value we take out of it, to get back to the original sign.

Answer 2

I think you are looking instead for a sorted linked list in this case, I modify someone I found here so it will insert with ascending order (I added the pop function, for some reason it wasn't in the code, but I think you may need it):

# 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()

As you can see, it was just change the >= to <=, it does the job perfectly