Testing Heap

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)

Have a look at the definition of heaps:

        http://en.wikipedia.org/wiki/Heap_%28data_structure%29

This should clarify matters.

Cheers,
   - Andreas

Nicolas Melin wrote:

Von: Nicolas Melin <[hidden email]> wrote:

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