1

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?

1

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.

  • Inlining? This is python. – noɥʇʎԀʎzɐɹƆ Jun 12 '16 at 15:01
  • Exactly. C++ would do this via templates. But in Python, you need to manually inline by copying this tiny function in-place. – Anony-Mousse Jun 12 '16 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? – noɥʇʎԀʎzɐɹƆ Jun 18 '16 at 18:24
  • Copy-and-pasting would reduce speed because it's written in C++ – noɥʇʎԀʎzɐɹƆ Jun 18 '16 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. – Anony-Mousse Jun 18 '16 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.