Tim Peters <t...@python.org> added the comment:
For history, note that `bisect` doesn't always work in this context either: a heap is NOT always in sorted order. For example, this is "a (min) heap" too: [1, 3, 2]. More, that's "the real" problem. If we could find the element to be removed in log(n) time, then it's possible to remove it from the heap in log(n) time too (you can, e.g., bubble elements up to fill the interior hole, then move the last heap element into the leaf hole that may leave behind and possibly sift it up to restore the heap property; and each of those phases takes log(n) time). ---------- nosy: +tim.peters _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue35659> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
