Created
June 12, 2020 15:33
-
-
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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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