0

Finding min or max value of an iterable (like keys of a dict, where keys are numbers) seems like the easiest thing in the world in Python:

my_dict = {2: 'v1', 4: 'v2', -1: 'v3'}
min(my_dict) # -> -1
max(my_dict) # -> 4

However, it feels like (it's mentioned here) that min and max always work on iterables, thus ensuring at least Ω(n) complexity.

But we are working with hash tables here, aren't we? Can't we make use of this fact and reduce complexity to O(1) or at least to O(log n)?

heinwol
  • 438
  • 4
  • 10
  • 2
    Do hash tables really help with min/max retrieval speed? There are obvious performance gains to using a hash table such as retrieving or adding. However, I don't see how a hash table could help you find the min or max value. Good hash functions randomly distribute values evenly so there is no inherit knowledge of min or max. It seems the only way to find the min/max is to at least iterate the whole hash table i.e. O(n). – purple Jul 24 '21 at 15:04
  • 1
    Hashing makes lookup of a known item O(1), but doesn't help you with comparison operations. If you want quick retrieval of min/max you might want to add heaps to the data structure (which will incur a cost when you add/remove items). – Samwise Jul 24 '21 at 15:06
  • @purple @Samwise, I see, that's my bad for not knowing this kind of data structure at a decent level. I could just use sth like binary heap then. Are there any builtin implementations of such things? I can only see `deque` in `collections` module, that won't go. P.S. One of you can answer the question, then i'll mark it. – heinwol Jul 24 '21 at 15:13
  • 2
    Check out https://docs.python.org/3/library/heapq.html and https://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python/40455775 – Samwise Jul 24 '21 at 15:19
  • @Samwise, thanks a bunch! That's exactly what i need! – heinwol Jul 24 '21 at 15:22

0 Answers0