COIN-OR::LEMON - Graph Library

Opened 8 years ago

Last modified 8 years ago

#313 new enhancement

Revise the implementation of PairingHeap and RadixHeap

Reported by: kpeter Owned by: alpar
Priority: major Milestone:
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

The implementation of PairingHeap and RadixHeap should be revised, since they could most likely be made more efficient.

For example, in LEDA (according to their tests) pairing heap is always faster than Fibonacci heap, moreover it is usually faster than binary heap. Radix heap is also very fast, it is usually better than both pairing and binary heaps. However according to my tests, PairingHeap and RadixHeap are almost always slower than BinHeap in LEMON.

LEDA results: http://www.cs.elte.hu/~kiraly/sanyag.adatstr/LEDAbook.heaps.ps

Two hints for PairingHeap:

  1. It does not contain the heuristic that the small heaps created by push() and decrease() operations are collected in a temporary storage and they are merged into the main heap only if it is necessary (e.g. in case of a pop() or prio()).
  2. The underlying binary tree is currently stored using two indices (pointers) and a bool value at each node. This needs less space than storing three indices (for the parent and the two children), but it is not clear if it is faster or slower. The latter representation should also be implemented and tested.

Apart from that, there could be other points in which the code could be made better.

Attachments (1)

heap_benchmark_results.txt (2.0 KB) - added by kpeter 8 years ago.

Download all attachments as: .zip

Change History (2)

Changed 8 years ago by kpeter

comment:1 Changed 8 years ago by kpeter

I attached a test file with benchmark results. The tests were performed on lime.cs.elte.hu with gcc 4.1, -O2.

Note: See TracTickets for help on using tickets.