• Heikki Linnakangas's avatar
    Fix a bug in pairing heap removal code. · 931bf3eb
    Heikki Linnakangas authored
    After removal, the next_sibling pointer of a node was sometimes incorrectly
    left to point to another node in the heap, which meant that a node was
    sometimes linked twice into the heap. Surprisingly that didn't cause any
    crashes in my testing, but it was clearly wrong and could easily segfault
    in other scenarios.
    
    Also always keep the prev_or_parent pointer as NULL on the root node. That
    was not a correctness issue AFAICS, but let's be tidy.
    
    Add a debugging function, to dump the contents of a pairing heap as a
    string. It's #ifdef'd out, as it's not used for anything in any normal
    code, but it was highly useful in debugging this. Let's keep it handy for
    further reference.
    931bf3eb
pairingheap.c 7.69 KB