id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc	revision
313	Revise the implementation of  PairingHeap and RadixHeap	Peter Kovacs	Alpar Juttner	"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."	enhancement	new	major		core	hg main