CODEWITHSUNDEEP
pythonlistsortingqueue
Fat Cat
Fat Cat

Reputation: 63

How do I sort a list of list to retain the item with the highest priority? (Python)

I am trying to make a Priority Queue that takes in input that contains a dequeue or enqueue operation then the value followed by the priority might look like:

enqueue 2 2
enqueue 1 3
enqueue 5 1
enqueue 6 2 
dequeue 
dequeue
dequeue
dequeue

I have this code at the start that sorts this by the order of priority:

from queue import Queue

data=[]
while True: 
    operation = input()
    if operation == "":
        break
    data.append(operation.split(" "))

data2=[]
data3=[]
for i in data: #separated into two list as not to get an out of range error when sorting 
    if "enqueue" in i: 
         data2.append(i)
    else:
         data3.append(i)


data2=sorted(data2,key=lambda x: int(x[2]))

data2=data2[::-1] #reversed to make it easier to order it by the highest priority

data=data2+data3 #put the enqueue and dequeue inputs together again

q=[]

for i in data:
    if "enqueue" in i: #add to the queue by priority
        q.append(i[1])
    if "dequeue" in i: #dequeue by priority
        print (q[0])
        del q[0]

My problem right now is that in the case of having the same priority, it should follow the first-in-first-out principle but since I sorted it, the initial order got lost. So I would have a list like:

So I would have a list like:

[['enqueue', '1', '3'], ['enqueue', '6', '2'], ['enqueue', '2', '2'], ['enqueue', '5', '1']]

And it would output:

1
6
2
5

Instead of:

1
2
6
5

How can I change the sorting such that it sorts the items by the highest priority but keep the initial order of those with the same priority? Thank you in advance.

Upvotes: 0

Views: 279

Answers (1)

Marco
Marco

Reputation: 887

To solve your problem, instead of reversing data2 after sorting, add the parameter reverse = True to your sorted call.

This happens because python sorting is stable, and will keep the original order when sorting. If you reverse the list after sorting, it will also reverse the original order.

>>> data2 = sorted(data2, key = lambda x: int(x[2]), reverse = True)
>>> print(data2)
[['enqueue', '1', '3'], ['enqueue', '2', '2'], ['enqueue', '6', '2'], ['enqueue', '5', '1']]

Upvotes: 2

Related Questions