--- a/Heap.st Thu Nov 19 16:40:11 2009 +0100
+++ b/Heap.st Fri Nov 27 22:18:23 2009 +0100
@@ -7,7 +7,16 @@
category:'Collections-Sequenceable'
!
-Heap comment:'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.
Instance variables:
array <Array> the data repository
tally <Integer> the number of elements in the heap
sortBlock <Block|nil> a two-argument block defining the sort order,
or nil in which case the default sort order is
[:element1 :element2| element1 <= element2]'
+Heap comment:'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.
+Instance variables:
+ array <Array> the data repository
+ tally <Integer> the number of elements in the heap
+ sortBlock <Block|nil> a two-argument block defining the sort order,
+ or nil in which case the default sort order is
+ [:element1 :element2| element1 <= element2]'
!
@@ -70,7 +79,7 @@
Note: This is the kind of benchmark a heap is designed for.
[exBegin]
| n rnd array time sorted |
- n := 5000.
+ n := 50000.
rnd := Random new.
array := (1 to: n) collect:[:i| rnd next].
@@ -95,7 +104,7 @@
SortedCollection (using the quick-sort algorithm) and
[exBegin]
| n rnd array out time sorted |
- n := 10000.
+ n := 40000.
rnd := Random new.
array := (1 to: n) collect:[:i| rnd next].
@@ -356,5 +365,9 @@
!Heap class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic2/Heap.st,v 1.1 2007-05-31 12:51:48 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic2/Heap.st,v 1.2 2009-11-27 21:18:23 cg Exp $'
+!
+
+version_CVS
+ ^ '$Header: /cvs/stx/stx/libbasic2/Heap.st,v 1.2 2009-11-27 21:18:23 cg Exp $'
! !