equal
deleted
inserted
replaced
9 |
9 |
10 Heap comment:'Class Heap implements a special data structure commonly referred to as ''heap''. Heaps are more efficient than SortedCollections if: |
10 Heap comment:'Class Heap implements a special data structure commonly referred to as ''heap''. Heaps are more efficient than SortedCollections if: |
11 a) Elements are only removed at the beginning |
11 a) Elements are only removed at the beginning |
12 b) Elements are added with arbitrary sort order. |
12 b) Elements are added with arbitrary sort order. |
13 The sort time for a heap is O(n log n) in all cases. |
13 The sort time for a heap is O(n log n) in all cases. |
14 |
|
15 Instance variables: |
14 Instance variables: |
16 array <Array> the data repository |
15 array <Array> the data repository |
17 tally <Integer> the number of elements in the heap |
16 tally <Integer> the number of elements in the heap |
18 sortBlock <Block|nil> a two-argument block defining the sort order, |
17 sortBlock <Block|nil> a two-argument block defining the sort order, |
19 or nil in which case the default sort order is |
18 or nil in which case the default sort order is |
78 Create a sorted collection of numbers, remove the elements |
77 Create a sorted collection of numbers, remove the elements |
79 sequentially and add new objects randomly. |
78 sequentially and add new objects randomly. |
80 Note: This is the kind of benchmark a heap is designed for. |
79 Note: This is the kind of benchmark a heap is designed for. |
81 [exBegin] |
80 [exBegin] |
82 | n rnd array time sorted | |
81 | n rnd array time sorted | |
83 n := 5000. |
82 n := 50000. |
84 rnd := Random new. |
83 rnd := Random new. |
85 array := (1 to: n) collect:[:i| rnd next]. |
84 array := (1 to: n) collect:[:i| rnd next]. |
86 |
85 |
87 time := Time millisecondsToRun:[ |
86 time := Time millisecondsToRun:[ |
88 sorted := Heap withAll: array. |
87 sorted := Heap withAll: array. |
103 |
102 |
104 Sort a random collection of Floats and compare the results with |
103 Sort a random collection of Floats and compare the results with |
105 SortedCollection (using the quick-sort algorithm) and |
104 SortedCollection (using the quick-sort algorithm) and |
106 [exBegin] |
105 [exBegin] |
107 | n rnd array out time sorted | |
106 | n rnd array out time sorted | |
108 n := 10000. |
107 n := 40000. |
109 rnd := Random new. |
108 rnd := Random new. |
110 array := (1 to: n) collect:[:i| rnd next]. |
109 array := (1 to: n) collect:[:i| rnd next]. |
111 |
110 |
112 out := Array new: n. |
111 out := Array new: n. |
113 time := Time millisecondsToRun:[ |
112 time := Time millisecondsToRun:[ |
364 ! ! |
363 ! ! |
365 |
364 |
366 !Heap class methodsFor:'documentation'! |
365 !Heap class methodsFor:'documentation'! |
367 |
366 |
368 version |
367 version |
369 ^ '$Header: /cvs/stx/stx/libbasic2/Heap.st,v 1.1 2007-05-31 12:51:48 cg Exp $' |
368 ^ '$Header: /cvs/stx/stx/libbasic2/Heap.st,v 1.2 2009-11-27 21:18:23 cg Exp $' |
370 ! ! |
369 ! |
|
370 |
|
371 version_CVS |
|
372 ^ '$Header: /cvs/stx/stx/libbasic2/Heap.st,v 1.2 2009-11-27 21:18:23 cg Exp $' |
|
373 ! ! |