Descending using heapq

Question

I use the Python heapq module to get data in ascending and descending order.

To grow , I use a minimal heap and it works well, as it should:

>>> 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 the top-down , I tried using different approaches, but they all have some drawback:

• Using a negative value as a priority to get reverse sorting. I have to use a separate list to reuse the data. If the source list is large, having a copy of the list is expensive.

   >>> 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 

• Using a tuple with a negative value as a priority is also a waste of space. I would not want to store the int list as a 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 

• Using the key to sort in heapify is missing. Sort of:

   >>> 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 

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

   >>> 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 a way to get a decreasing order similar to how I got an increasing order? :)

Answer 1

As we discussed in the comments, your concerns about copying data when using negative values ​​to flip the mini-heap to the max-heap do not matter when you start with an empty heap and add values ​​as you go, since this use case is finding the current median of the value stream, negating the values ​​as they are added should work fine.

Here's the middle generator that I wrote to just check if it works as 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 (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 values ​​of less than or equal to-median. Each value is negated when it is pushed, so using the usual mini-heap operations makes it work like the maximum heap. We just need to remember to undo again any value that we pull out of it in order to return to the original sign.

Answer 2

I think that you are looking for a sorted linked list in this case, I am modifying someone I found here to be inserted with an ascending order (I added a pop function, for some reason it was not in the code, but I I think you may need this):

 # 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, this is just a change> = to <=, it does a great job