Can you give some examples where it's having problems? Perhaps we can figure out what's going on. To be fair, I haven't used Heap.pm, but I did notice that it's tests are not terribly comprehensive, so I'm not surprised. I confess a desire to see what's not working and start writing tests for it :)
If you happen to have a copy of "Mastering Algorithms with Perl", by O'Reilly, they have a heap implementation in there along with an excellent discussion. Perhaps rolling your own my help?
New address of my CGI Course.
Silence is Evil (feel free to copy and distribute widely - note copyright text)