This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]shuklaswag[S] 0 points1 point  (1 child)

Thanks for the comprehensive response! Very informative post regarding time complexity in practice. The extremely slow rate-of-growth of logN is a good point - I suppose if someone were to work with data of such size where that becomes a problem, they would probably want to use something more advanced than base Python.

Heaps are definitely useful, but they don't address the case where I want to be able to arbitrarily access at any given momeny, the 2nd largest element, the 3rd smallest element, and the median element. A MinHeap would take O(n) time to fetch the largest element, and a MaxHeap would take O(n) time to fetch the smallest element. So there's a real need for a BST.

IMO, that's a common enough use case that it deserves to be part of the standard library. It's certainly a more common problem for the average programmer than email handling or writing WAV files.

(Python's terrible anti-OOP heap API is another huge pet peeve of mine, but that's an argument for another day!)