Descending order using heapq
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
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.