Skip to content

Instantly share code, notes, and snippets.

@applenob
Created June 13, 2018 08:48
Show Gist options
  • Save applenob/38561d91859a632922930570da1560a7 to your computer and use it in GitHub Desktop.
Save applenob/38561d91859a632922930570da1560a7 to your computer and use it in GitHub Desktop.
Keep top n number in a list with ascend order.
class TopQueue:
"""keep top n num in a list with ascend order."""
def __init__(self, n):
self.n = n
self.queue = []
def add(self, new_val):
bigger_index = -1
for i, one in enumerate(self.queue):
if one > new_val:
bigger_index = i
break
if bigger_index == -1:
# no one in the queue is bigger than the new val
if len(self.queue) == self.n:
del self.queue[0]
self.queue.append(new_val)
return True
if bigger_index == 0:
# the first one in the queue is bigger than the new val
if len(self.queue) == self.n:
return False
self.queue.insert(0, new_val)
return True
else:
# someone in the queue is bigger than the new val
if len(self.queue) == self.n:
del self.queue[0]
self.queue.insert(bigger_index - 1, new_val)
else:
self.queue.insert(bigger_index, new_val)
return True
def get_queue(self):
return self.queue
def test_TopQueue():
tq = TopQueue(3)
print(tq.add(1))
print(tq.get_queue())
print(tq.add(0))
print(tq.get_queue())
print(tq.add(2))
print(tq.get_queue())
print(tq.add(3))
print(tq.get_queue())
print(tq.add(2))
print(tq.get_queue())
print(tq.add(3))
print(tq.get_queue())
print(tq.add(3))
print(tq.get_queue())
print(tq.add(1))
print(tq.get_queue())
print(tq.add(4))
print(tq.get_queue())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment