logoalt Hacker News

StellarScienceyesterday at 3:42 PM1 replyview on HN

Python is famously built around hash tables. So much so that several versions ago they made an improvement to the hash table implementation, and the entire language became several percent faster.

However, I'm surprised to see no data structures at all with O(log(N)) complexity. Surely there are some use cases for which that's desirable?


Replies

krautsaueryesterday at 5:09 PM

One reason you don't see a data structure with O(log(n)) operations in this list is that priority queues/heaps are not a built-in type. Weirdly, there isn't a type for them at all, just a bunch of functions (good luck if you use them wrong). https://docs.python.org/3/library/heapq.html

show 2 replies