Class: Heap

• Inheritance
• Description
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • adding
  • comparing
  • enumerating
  • growing
  • private
  • private-heap
  • queries
  • removing
  • testing
• Examples

Inheritance:

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

Package:

stx:libbasic2

Category:

Collections-Sequenceable

Version:

rev: 1.15 date: 2024/02/23 08:55:52

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]

copyright
COPYRIGHT (c) 2018 by eXept Software AG
             All Rights Reserved

This software is furnished under a license and may be used
only in accordance with the terms of that license and with the
inclusion of the above copyright notice.   This software may not
be provided or otherwise made available to, or used by, any
other person.  No title to or ownership of the software is
hereby transferred.

Class protocol:

 new

(comment from inherited method)
return an instance of myself without indexed variables

 new: n

(comment from inherited method)
return an instance of myself with anInteger indexed variables

 sortBlock: aBlock

Create a new heap sorted by the given block

 withAll: aCollection

Create a new heap with all the elements from aCollection

 withAll: aCollection sortBlock: sortBlock

Create a new heap with all the elements from aCollection

Instance protocol:

 at: index

Return the element at the given position within the receiver

 at: index put: newObject

Heaps are accessed with #add: not #at:put:

 first

Return the first element in the receiver

Usage example(s):

Heap new first

 firstOrNil

(comment from inherited method)
return the first element or nil, if the collection is empty.

 reSort

Resort the entire heap

 size

Answer how many elements the receiver contains.

 sortBlock

 sortBlock: aBlock

 add: anObject

Include newObject as one of the receiver's elements. Answer newObject.

 = anObject

(comment from inherited method)
return true if the receiver and aCollection represent collections
with equal contents, and if they are of the same species.

 do: aBlock

Evaluate aBlock with each of the receiver's elements as the argument.

 grow

Become larger.

 growSize

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

 growTo: newSize

Grow to the requested size.

 trim

Remove any empty slots in the receiver.

 array

 privateRemoveAt: index

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

 setCollection: aCollection

 setCollection: aCollection tally: newTally

 species

 downHeap: anIndex

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

 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.

 upHeap: anIndex

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

 isEmpty

Answer whether the receiver contains any elements.

 sorts: element1 before: element2

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

 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)

 removeFirst

Remove the first element from the receiver

 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.

 removeIndex: index

Remove the element at given position

 isFixedSize

return true if the receiver cannot grow

 isHeap

Examples:

    | 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'.

    | 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'.