COIN-OR::LEMON - Graph Library

Opened 15 years ago

Last modified 15 years ago

#313 new enhancement

Revise the implementation of PairingHeap and RadixHeap

Reported by: Peter Kovacs Owned by: Alpar Juttner
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 Peter Kovacs 15 years ago.

Download all attachments as: .zip

Change History (2)

Changed 15 years ago by Peter Kovacs

Attachment: heap_benchmark_results.txt added

comment:1 Changed 15 years ago by Peter Kovacs

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.