python-3.xheap

Heap argument must be a list in python 3


I was trying to implement a data structure that returns a value such that set (key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp. I tried to use a heapq in Python. It raised an exception that I don't understand.

class TimeMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.mapping = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.mapping[key].append([-timestamp, value])
        

    def get(self, key: str, timestamp: int) -> str :
        if not self.mapping[key]:
            return ''
        heap = heapq.heapify(self.mapping[key])
        for pre_stamp, val in heapq.heappop(heap):
            if -pre_stamp <= timestamp:
                return val
        return '' 
        

The exception was: heap argument must be a list.

But it looks the mapping[key] returned value is a list.


Solution

  • The fact that self.mapping is defined as collections.defaultdict(list) does not mean that self.mapping[key] will return a list for every arbitrary key. It just means that self.mapping[key] will return a list for every key that does not exist will return an empty list.

    import collections
    
    d = collections.defaultdict(list)
    d['a'] = 'not a list'
    print(type(d['a']), d['a'])
    

    outputs

    <class 'str'> not a list