The builtin heapq library in Python only supports min-heaps and is implemented in pure python, which makes it quite slow. Is there a decent heap library the supports both min-heaps and max-heaps and is written in C?
Add a comment
|
1 Answer
Heap functionality is so tiny, it should be inlined whenever possible. In python, this means copy&paste (I'm not aware of Python automatically inlining small functions, like Java does).
Whatever library you use, it will come at a non-neglibile invocation overhead. More than just putting the code (specific for your problem) inline. To really improve things, convert your code to Cython then.
answered Jun 12, 2016 at 10:18
-
-
Exactly. C++ would do this via templates. But in Python, you need to manually inline by copying this tiny function in-place. Commented Jun 12, 2016 at 15:08
-
Apparently, CPython contains a C++ implementation too. Wouldn't PyPy or Cython in pure python mode + type annotations be a better solution? Commented Jun 18, 2016 at 18:24
-
Copy-and-pasting would reduce speed because it's written in C++ Commented Jun 18, 2016 at 18:28
-
In C++ it does not matter. You would use a template in C++ which is effectively inlined, too. The compiler can optimize this well once you have safe types. The main bottleneck is due to duck typing. Commented Jun 18, 2016 at 18:53