Port fourary, d-ary, pairing and binomial heaps

[Peter Kovacs]

Dorian Batha implemented fourary, d-ary, pairing and binomial heaps in LEMON (for his BSc thesis). These structures should also be ported.

[Peter Kovacs]

Port + improvements

[Peter Kovacs]

The attached bundle file contains the port of these tools with improvements and unification for the doc and the member names. They seem to be clear enough to add to the main repository.

[Peter Kovacs]

I attached two more changesets on the top of the bundle file: [7124b2581f72] and [39a5b48bcace].

[Peter Kovacs]

Some questions about the name of the heaps:

• The name KaryHeap seems to be strange for me. What about the followings: DaryHeap, KHeap, DHeap? Would any of them be better? Maybe "d-ary" is used more than "k-ary", but e.g. in LEDA it is called k_heap.
• FouraryHeap: is this name suitable? Should we keep this structure at all?
• Maybe BinomHeap is to close to BinHeap. What about BinomialHeap? (I think, short names should be used for the best known and/or most widely used ones, e.g. BinHeap, FibHeap)

[Peter Kovacs]

[9314d9339475] improves the bubbleDown() function of FouraryHeap and KaryHeap. It performs less comparison (like the current implementation of the binary heap). It proved to be slightly faster on average, but in case of FouraryHeap and -O3 optimization it could be 10-25 percent faster.

[Peter Kovacs]

According to benchmark tests, the implementation of PairingHeap and RadixHeap could/should be improved (e.g. FibHeap usually outperforms PairingHeap), however they are rahter good.

On the other hand, BinomHeap is extremly slow when it is used as a Dijkstra heap, though it is good in heap sort. Thus I suppose that something is wrong in its implementation, probably in decrease(). Maybe this structure could be omitted until this problem is investigated.

[Peter Kovacs]

Replying to kpeter:

On the other hand, BinomHeap is extremly slow when it is used as a Dijkstra heap, though it is good in heap sort. Thus I suppose that something is wrong in its implementation, probably in decrease(). Maybe this structure could be omitted until this problem is investigated.

[3887d6f994d7] fixes this problem. It provides a much faster implementation for decrease() and also improves the performance of push() and pop(). With these improvements this class could also be merged into the main branch. It is still not so fast, but it is comparable with the other heaps.

[Peter Kovacs]

All the changesets related to this ticket went to the main branch. Alpar, thank you.

However note that the doc of these heaps was written supposing that the changesets in #299 will also be applied (e.g. creating an own group for heaps).

The only questions left here are about the names of the heaps:

Some questions about the name of the heaps:

• The name KaryHeap seems to be strange for me. What about the followings: DaryHeap, KHeap, DHeap? Would any of them be better? Maybe "d-ary" is used more than "k-ary", but e.g. in LEDA it is called k_heap.
  
• FouraryHeap: is this name suitable? Should we keep this structure at all?
  
• Maybe BinomHeap is to close to BinHeap. What about BinomialHeap? (I think, short names should be used for the best known and/or most widely used ones, e.g. BinHeap, FibHeap)

[Peter Kovacs]

KHeap or DHeap -- which one should we use instead of KaryHeap?

FouraryHeap -- alternatives could be: QuaternaryHeap, QuadHeap, QuatHeap, QuaHeap, QHeap, FourHeap, FHeap. Should we keep it at all?

What do you think?

[Peter Kovacs]

[65a0521e744e] renames three of the new heaps:

• KaryHeap --> DHeap
• FouraryHeap --> QuadHeap
• BinomHeap --> BinomialHeap

What do you think? Are these names acceptable?

[Balazs Dezso]

In my opinion, the binomial heap doesn't have to be merged to the trunk, because I think it does not provide any advantages comparing to the other implementations. In addition, the main advantage of the binomial heaps, i.e. they can be merged in logarithmic time, is not implemented, and the interface cannot be extended to provide this feature.

[Alpar Juttner]

Replying to deba:

In my opinion, the binomial heap doesn't have to be merged to the trunk, because I think it does not provide any advantages comparing to the other implementations. In addition, the main advantage of the binomial heaps, i.e. they can be merged in logarithmic time, is not implemented, and the interface cannot be extended to provide this feature.

Could you please remind me of the use of logarithmic time merge?

[Peter Kovacs]

Replying to alpar:

Could you please remind me of the use of logarithmic time merge?

See ​http://en.wikipedia.org/wiki/Binomial_heap#Merge.

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

Could you please remind me of the use of logarithmic time merge?

See ​http://en.wikipedia.org/wiki/Binomial_heap#Merge.

It's only me who can't see anything about the _use_ of logarithmic time merge at this link?

[Peter Kovacs]

Replying to alpar:

It's only me who can't see anything about the _use_ of logarithmic time merge at this link?

I'm sorry. I misread your sentence, I did not catch the word "use". Btw. I know nothing about the usage.

[Peter Kovacs]

Two questions left here:

1. Names of the heaps. What do yout think about these renamings?
   • KaryHeap --> DHeap
   • FouraryHeap --> QuadHeap
   • BinomHeap --> BinomialHeap

2. Do we need BinomialHeap at all (supposing that we don't and won't have merge operation for that)? Should we keep it despite this lack of functionality or should we remove it? (It could be kept in e.g. a contribution project.)

[Alpar Juttner]

Replying to kpeter:

Two questions left here:

1. Names of the heaps. What do yout think about these renamings?
   • KaryHeap --> DHeap
   • FouraryHeap --> QuadHeap
   • BinomHeap --> BinomialHeap

I agree with them all.

2. Do we need BinomialHeap at all (supposing that we don't and won't have merge operation for that)?

Could anyone elaborate why is this merge operation important?

Should we keep it despite this lack of functionality or should we remove it?

I see no problem with keeping it in the core, if the code is otherwise up to the usual standards.

[Peter Kovacs]

Replying to alpar:

1. Names of the heaps. What do yout think about these renamings?
   • KaryHeap --> DHeap
   • FouraryHeap --> QuadHeap
   • BinomHeap --> BinomialHeap

I agree with them all.

Okay. Then what about applying [65a0521e744] and close this ticket?

2. Do we need BinomialHeap at all (supposing that we don't and won't have merge operation for that)?

Could anyone elaborate why is this merge operation important?

Maybe Balazs could answer this question. He was the supervisor of Dorian Batha, who developed this stucture and Balazs doubted whether we should keep this heap.

Should we keep it despite this lack of functionality or should we remove it?

I see no problem with keeping it in the core, if the code is otherwise up to the usual standards.

Both its interface and its implementation is clear, and its performance is relatively good (sine [3887d6f994d7]).

[Alpar Juttner]

Replying to kpeter:

Okay. Then what about applying [65a0521e744] and close this ticket?

Done.