eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'Heap':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: Heap


Inheritance:

   Object
   |
   +--Collection
      |
      +--SequenceableCollection
         |
         +--Heap

Package:
stx:libbasic2
Category:
Collections-Sequenceable
Version:
rev: 1.9 date: 2019/02/10 13:51:26
user: cg
file: Heap.st directory: libbasic2
module: stx stc-classLibrary: libbasic2

Description:


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]


Class protocol:

examples
o  documentation
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]

o  examples
Create a sorted collection of numbers, remove the elements
sequentially and add new objects randomly.
Note: This is the kind of benchmark a heap is designed for.
[exBegin]
| n rnd array time sorted |
n := 50000.
rnd := Random new.
array := (1 to: n) collect:[:i| rnd next].

time := Time millisecondsToRun:[
sorted := Heap withAll: array.
1 to: n do:[:i|
sorted removeFirst.
sorted add: rnd next].
].
Transcript showCR:'Time for Heap: ', time printString,' msecs'.

time := Time millisecondsToRun:[
sorted := SortedCollection withAll: array.
1 to: n do:[:i|
sorted removeFirst.
sorted add: rnd next].
].
Transcript showCR:'Time for SortedCollection: ', time printString,' msecs'.
[exEnd]

Sort a random collection of Floats and compare the results with
SortedCollection (using the quick-sort algorithm) and
[exBegin]
| n rnd array out time sorted |
n := 40000.
rnd := Random new.
array := (1 to: n) collect:[:i| rnd next].

out := Array new: n.
time := Time millisecondsToRun:[
sorted := Heap withAll: array.
1 to: n do:[:i| sorted removeFirst].
].
Transcript showCR:'Time for heap-sort: ', time printString,' msecs'.

time := Time millisecondsToRun:[
sorted := SortedCollection withAll: array.
].
Transcript showCR:'Time for quick-sort: ', time printString,' msecs'.
[exEnd]

instance creation
o  new

o  new: n

o  sortBlock: aBlock
Create a new heap sorted by the given block

o  withAll: aCollection
Create a new heap with all the elements from aCollection

o  withAll: aCollection sortBlock: sortBlock
Create a new heap with all the elements from aCollection


Instance protocol:

accessing
o  at: index
Return the element at the given position within the receiver

o  at: index put: newObject
Heaps are accessed with #add: not #at:put:

o  first
Return the first element in the receiver

usage example(s):

      Heap new first

o  firstOrNil

o  reSort
Resort the entire heap

o  size
Answer how many elements the receiver contains.

o  sortBlock

o  sortBlock: aBlock

adding
o  add: anObject
Include newObject as one of the receiver's elements. Answer newObject.

comparing
o  = anObject

enumerating
o  do: aBlock
Evaluate aBlock with each of the receiver's elements as the argument.

growing
o  grow
Become larger.

o  growSize
Return the size by which the receiver should grow if there are no empty slots left.

o  growTo: newSize
Grow to the requested size.

o  trim
Remove any empty slots in the receiver.

private
o  array

o  privateRemoveAt: index
Remove the element at the given index and make sure the sorting order is okay.
Return the removed object

o  setCollection: aCollection

o  setCollection: aCollection tally: newTally

o  species

private-heap
o  downHeap: anIndex
Check the heap downwards for correctness starting at anIndex.
Everything above (i.e. left of) anIndex is ok.

o  downHeapSingle: anIndex
This version is optimized for the case when only one element in the receiver can be at a wrong position. It avoids one comparison at each node when travelling down the heap and checks the heap upwards after the element is at a bottom position. Since the probability for being at the bottom of the heap is much larger than for being somewhere in the middle this version should be faster.

o  upHeap: anIndex
Check the heap upwards for correctness starting at anIndex.
Everything below anIndex is ok.

queries
o  isEmpty
Answer whether the receiver contains any elements.

o  sorts: element1 before: element2
Return true if element1 should be sorted before element2.
This method defines the sort order in the receiver

removing
o  remove: oldObject ifAbsent: aBlock
Remove the first occurrence of oldObject as one of the receiver's elements.
If several of the elements are equal to oldObject, only one is removed.
If no element is equal to oldObject, answer the result of evaluating anExceptionBlock.
Otherwise, answer the removed object
(which may be non-identical, but equal to oldObject)

o  removeAt: index
Remove the element at given position

o  removeFirst
Remove the first element from the receiver

o  removeIdentical: oldObject ifAbsent: aBlock
Remove the first occurrence of oldObject as one of the receiver's elements.
If oldObject is present multiple times, only the first occurrence is removed.
If oldObject is not present, answer the result of evaluating anExceptionBlock.
Otherwise, answer the argument, oldObject.

testing
o  isFixedSize
return true if the receiver cannot grow

o  isHeap


Examples:


Create a sorted collection of numbers, remove the elements sequentially and add new objects randomly. Note: This is the kind of benchmark a heap is designed for.
    | n rnd array time sorted |
    n := 50000. 
    rnd := Random new.
    array := (1 to: n) collect:[:i| rnd next].

    time := Time millisecondsToRun:[
            sorted := Heap withAll: array.
            1 to: n do:[:i| 
                    sorted removeFirst.
                    sorted add: rnd next].
    ].
    Transcript showCR:'Time for Heap: ', time printString,' msecs'.

    time := Time millisecondsToRun:[
            sorted := SortedCollection withAll: array.
            1 to: n do:[:i| 
                    sorted removeFirst.
                    sorted add: rnd next].
    ].
    Transcript showCR:'Time for SortedCollection: ', time printString,' msecs'.
Sort a random collection of Floats and compare the results with SortedCollection (using the quick-sort algorithm) and
    | n rnd array out time sorted |
    n := 40000. 
    rnd := Random new.
    array := (1 to: n) collect:[:i| rnd next].

    out := Array new: n. 
    time := Time millisecondsToRun:[
            sorted := Heap withAll: array.
            1 to: n do:[:i| sorted removeFirst].
    ].
    Transcript showCR:'Time for heap-sort: ', time printString,' msecs'.

    time := Time millisecondsToRun:[
            sorted := SortedCollection withAll: array.
    ].
    Transcript showCR:'Time for quick-sort: ', time printString,' msecs'.


ST/X 7.2.0.0; WebServer 1.670 at bd0aa1f87cdd.unknown:8081; Tue, 19 Mar 2024 08:18:20 GMT