Testing Heap

"Boris Gärtner" Boris.Gaertner at gmx.net
Wed Mar 8 09:42:52 UTC 2006


Von: Nicolas Melin <n.melin at microkwen.com> wrote:


> Heap class comments say :
> 
> Class Heap implements a special data structure commonly referred to as
> 'heap'. Heaps are more efficient than SortedCollections if:
> a) Elements are only removed at the beginning
> b) Elements are added with arbitrary sort order.
> The sort time for a heap is O(n log n) in all cases.
> 
> I'm not sure I understand the comment: is Heap actually supposed to sort
> items, independently of the adding order ?
> 
> I'm trying to do this: (Heap withAll: #(1 3 5 7 11 9 10))
> and the result is: a Heap(1 3 5 7 11 9 10)
> 
> 
Please try this:

  | heap  stream |
 heap := Heap withAll: #(1 3 5 7 11 9 10).
 stream := WriteStream on: (Array new: heap size).
 [heap notEmpty]
     whileTrue: [stream nextPut: heap removeFirst.].
 stream contents 

You see that the heap delivers its elements sorted.

I think you were bitten by the fact that in the printString
of a heap its elements are not enumerated in the
sorting order. This is a property of Heap>>do:
That method does not enumerate the heap elements
in sorting order as you can see from this example:

  | heap  stream |
 heap := Heap withAll: #(1 3 5 7 11 9 10).
 stream := WriteStream on: (Array new: heap size).
 heap do: [:item | stream nextPut: item].
 stream contents.

This behavior of  do: is indeed questionable.

Greetings, 
Boris



More information about the Squeak-dev mailing list