Niko Schwarz <niko.schwarz at gmx.net> wrote:
	Cos I'm currently working on basic data structures, such as heaps.

Why?  Squeak already HAS heaps.
Open a Browser.
Class category "Collections-Sequencable".
You'll find Heap in the second pane.

	It's the same reason for which I came up with my MarkingKey: I use it e.g. to 
	mark the top of a heap, so that I never have to check if I go out of bounds. 
	But when the MarkingKey shall be the first element, then the "real" first 
	element must be number 2, and phew: it's really buggy to always access your 
	1st element as 2, the 3rd one as 4 and so on.

Smalltalk's existing Heap class manages just *fine* without any Sentinel
objects.  In fact, since you can supply your own comparison procedure
(the sortBlock instance variable) it is difficult to see how a generic
MarkingKey "feh!" could possibly work.

I have implemented heaps in about five different programming languages,
and have never found sentinels to be of any particular use.

Yes, they may save you the odd "index >= 1" comparison, BUT in real life,
your element comparison costs so much more, and the integer comparison
is so fast, that the saving is quite negligible.

	So, instead of my over beautiful snippet up there, I had to implement it like 
	this:
	
	replace: anElement 

Replacing is NOT an operation that one generally expects in a heap.
The basic priority queue operations are
    - create an empty priority queue
    - report a priority queue's size
    - add an element to a priority queue
    - remove the element with extremal priority
    - take the union of two priority queues
Heaps aren't very good at the last of these operations, which is why
binomial heaps and Fibonnacci heaps were invented.

I note that for very large in-memory priority queues, 4-way heaps
are known to perform better than 2-way heaps (better cache performance).
There are a host of other approaches which might suit Smalltalk well:
leftist heaps, perfectly balanced heaps, treaps, pagodas, ...