Skip to content

Instantly share code, notes, and snippets.

@zjplab
Created June 12, 2020 15:33
Show Gist options
  • Save zjplab/f206c57b15b3581d301192a744eb1b15 to your computer and use it in GitHub Desktop.
Save zjplab/f206c57b15b3581d301192a744eb1b15 to your computer and use it in GitHub Desktop.
Custom data type priority queue with maximum length(pop out automatically if exceeded)
from heapq import *
'''
Need to specify key function for custom data structures for comaprision in a min heap
'''
class _Wrapper:
def __init__(self, item, key):
self.item = item
self.key = key
def __lt__(self, other):
return self.key(self.item) < other.key(other.item)
def __eq__(self, other):
return self.key(self.item) == other.key(other.item)
#def __repr__(self):
# return str(self.item)
class KeyPriorityQueue:
def __init__(self, key, maxLen):
self.key = key
self.queue=[]
self.maxLen=maxLen
def _get(self):
wrapper = heappop(self.queue)
return wrapper.item
def get(self):
return self._get()
def peek(self):
return self.queue[0]
def _put(self, item):
heappush(self.queue, _Wrapper(item, self.key))
def put(self, item):
if(self._qsize() == self.maxLen):
heappop(self.queue)
self._put(item)
def _qsize(self):
return len(self.queue)
# testing scirpt
if __name__=='__main__':
data=[(3, 3.5556), (-2, -3), (100, 2)]
key= lambda x:x[1]
q=KeyPriorityQueue(key, 2)
for item in data:
q.put(item)
print(q.queue)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment