Here's a new version of the patch. It now uses the same pairing heap code that I posted in the other thread ("advance local xmin more aggressivley", http://www.postgresql.org/message-id/5488ACF0.8050901@vmware.com). The pairingheap_remove() function is unused in this patch, but it is needed by that other patch.
Under enable-cassert, this tries to call pairingheap_empty, but that function doesn't exist.
I looked in the other patch and didn't find it defined there, either.