[squeak-dev] Question about the Heap class.

> This might just belong on the newbies list, but... I'm looking at
> using a Heap for a primarily read-only, sorted set of some objects.
> Now, just to prefix this, I'm assuming the Heap is largely equivalent
> to the SortedCollection, in that it's intended to keep it's items in
> sorted order as they're added, and that accessing those items using
> the #at: selector will retrieve them in their sorted positions.
>
> So, that said, I have the following little code snippet:
>
> h := Heap new sortBlock: [ : a : b | a <= b ].  "Just to be explicit"
> r := Random new.
>
> 1 to: 10 do: [ : i | h add: (r nextInt: 1000000) ].
>
> h do: [ : i | Transcript show: i; cr ].
>
> Here's some example output:
>
> 90436
> 692737
> 206478
> 849361
> 825757
> 704772
> 262508
> 999388
> 971421
> 956498
>
> It ain't sorted.  So... thoughts? :)
>
> Brett.
>
>

>> Check out http://en.wikipedia.org/wiki/Binary_heap in particular the section
>> on Heap implementation which is directly applicable to the Heap class in
>> Squeak. Note that the heap property does not require the heap to be totally
>> sorted; the following two Heaps are both valid:
>
> Well, so much for the computing science degree (boy it's been a while
> since my last algorithms class :)... I was basing my assumption on the
> fact that the class comment for the Heap directly compares it to the
> SortedCollection class (in terms of complexity), which, to me, implies
> they are functionally equivalent.  After all, it's hardly fair
> comparing a fully sorted collection to an implementation that doesn't
> fully sort. :)
>
> Thanks!
>
> Brett.
>
>