Changes between Version 4 and Version 5 of BinaryHeapsCowan


Ignore:
Timestamp:
11/21/12 21:26:12 (5 years ago)
Author:
cowan
Comment:

Revised wording

Legend:

Unmodified
Added
Removed
Modified
  • BinaryHeapsCowan

    v4 v5  
    11== Binary heaps == 
    22 
    3 Binary heaps are mutable collections that can contain any Scheme object provided there exists a total ordering on the objects expressed by an ''ordering procedure''.  They are intended to be a thin veneer over arrays.  Binary heaps are disjoint from other types of Scheme objects. 
     3Binary heaps are mutable collections that can contain any Scheme object provided there exists a total ordering on the objects expressed by an ''ordering procedure''.  They are intended to be a thin veneer over vectors.  Binary heaps are disjoint from other types of Scheme objects. 
    44 
    55== Procedures == 
     
    77`(make-heap `''<''`)` 
    88 
    9 Constructs and returns a new empty heap.  ''<'' is the less-than procedure for the heap. 
     9Returns a newly allocated empty heap.  ''<'' is the less-than procedure for the heap. 
    1010 
    1111`(heap `''<''` `''element''` ...)` 
    1212 
    13 Constructs and returns a new heap using ''<'' as the ordering procedure, and containing the ''elements''.  This operation should be O(n) in the size of the heap. 
     13Returns a newly allocated heap using ''<'' as the ordering procedure, and containing the ''elements''.  This operation should be O(n) in the size of the heap. 
    1414 
    1515`(copy-heap` ''heap''`)` 
    1616 
    17 Constructs and returns a new heap containing the elements of ''heap'' with the same ''<'' procedure. 
     17Returns a newly allocated heap containing the elements of ''heap'' with the same ''<'' procedure. 
    1818 
    1919`(heap? `''obj''`)` 
     
    4343Removes the smallest element of the heap (according to the ''<'' function) and returns it.  This operation should be O(log N) in the size of the heap. 
    4444 
    45 '''Issue:''' maybe this should return an unspecified value like other destructive procedures? 
    46  
    4745`(heap-map `''proc''` `''<''` `''heap''`)` 
    4846 
    49 Applies ''proc'' to each element of ''heap'' in arbitrary order and constructs and returns a new heap with ordering predicate ''<'' containing the values of the applications.  This operation should be O(N) in the size of the heap. 
     47Applies ''proc'' to each element of ''heap'' in arbitrary order and returns a newly allocated heap with ordering predicate ''<'' containing the values of the applications.  This operation should be O(N) in the size of the heap. 
    5048 
    5149`(heap-for-each `''proc''` `''heap''`)` 
     
    5553`(heap->list `''heap''`)` 
    5654 
    57 Constructs and returns a new list containing the members of ''heap'' in arbitrary order.  This operation should be O(N) in the size of the heap. 
     55Returns a newly allocated list containing the members of ''heap'' in arbitrary order.  This operation should be O(N) in the size of the heap. 
    5856 
    5957`(heap->sorted-list! `''<''` `''heap''`)` 
    6058 
    61 Constructs and returns a new list containing the members of ''heap'' in increasing order.  ''Heap'' may be destroyed in the process. 
     59Returns a newly allocated list containing the members of ''heap'' in increasing order.  ''Heap'' may be destroyed in the process. 
    6260 
    6361`(list->heap `''<''` `''list''`)` 
    6462 
    65 Constructs and returns a new heap containing the elements of ''list'' and using ''<'' as the ordering procedure.  This operation should be O(n) in the size of the heap. 
     63Returns a newly allocated heap containing the elements of ''list'' and using ''<'' as the ordering procedure.  This operation should be O(n) in the size of the heap. 
    6664 
    6765`(heap->vector `''heap''`)` 
    6866 
    69 Constructs and returns a new vector containing the elements of ''heap'' in arbitrary order. 
     67Returns a newly allocated vector containing the elements of ''heap'' in arbitrary order. 
    7068 
    7169`(heap->sorted-vector! `''<''` `''heap''`)` 
    7270 
    73 Returns a vector containing the elements of ''heap'' in increasing order.  ''Heap'' may be destroyed in the process. 
     71Returns a newly allocated vector containing the elements of ''heap'' in increasing order.  ''Heap'' may be destroyed in the process. 
    7472 
    7573`(vector->heap `''<''` `''vector''`)` 
    7674 
    77 Constructs and returns a new heap containing the elements of ''vector'' and using ''<'' as the ordering procedure.  This operation should be O(n) in the size of the heap. 
    78  
     75Returns a newly allocated heap containing the elements of ''vector'' and using ''<'' as the ordering procedure.  This operation should be O(n) in the size of the heap.