tree 0fda8700a217e33f4244c08228f483c7f9148781
parent e3998c681dec35fe0de25f693a39de6fb881134e
author Dave Watson <davejwatson@fb.com> 1456773772 -0800
committer Jason Evans <je@fb.com> 1457473579 -0800

Pairing heap

Initial implementation of a twopass pairing heap with aux list.
Research papers linked in comments.

Where search/nsearch/last aren't needed, this gives much faster first(),
delete(), and insert().  Insert is O(1), and first/delete don't have to
walk the whole tree.

Also tested rb_old with parent pointers - it was better than the current
rb.h for memory loads, but still much worse than a pairing heap.

An array-based heap would be much faster if everything fits in memory,
but on a cold cache it has many more memory loads for most operations.