Changes between Version 4 and Version 5 of BinaryHeapsCowan
 Timestamp:
 11/21/12 21:26:12 (5 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

BinaryHeapsCowan
v4 v5 1 1 == Binary heaps == 2 2 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.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 vectors. Binary heaps are disjoint from other types of Scheme objects. 4 4 5 5 == Procedures == … … 7 7 `(makeheap `''<''`)` 8 8 9 Constructs and returns a newempty heap. ''<'' is the lessthan procedure for the heap.9 Returns a newly allocated empty heap. ''<'' is the lessthan procedure for the heap. 10 10 11 11 `(heap `''<''` `''element''` ...)` 12 12 13 Constructs and returns a newheap using ''<'' as the ordering procedure, and containing the ''elements''. This operation should be O(n) in the size of the heap.13 Returns 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. 14 14 15 15 `(copyheap` ''heap''`)` 16 16 17 Constructs and returns a newheap containing the elements of ''heap'' with the same ''<'' procedure.17 Returns a newly allocated heap containing the elements of ''heap'' with the same ''<'' procedure. 18 18 19 19 `(heap? `''obj''`)` … … 43 43 Removes 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. 44 44 45 '''Issue:''' maybe this should return an unspecified value like other destructive procedures?46 47 45 `(heapmap `''proc''` `''<''` `''heap''`)` 48 46 49 Applies ''proc'' to each element of ''heap'' in arbitrary order and constructs and returns a newheap with ordering predicate ''<'' containing the values of the applications. This operation should be O(N) in the size of the heap.47 Applies ''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. 50 48 51 49 `(heapforeach `''proc''` `''heap''`)` … … 55 53 `(heap>list `''heap''`)` 56 54 57 Constructs and returns a newlist containing the members of ''heap'' in arbitrary order. This operation should be O(N) in the size of the heap.55 Returns a newly allocated list containing the members of ''heap'' in arbitrary order. This operation should be O(N) in the size of the heap. 58 56 59 57 `(heap>sortedlist! `''<''` `''heap''`)` 60 58 61 Constructs and returns a newlist containing the members of ''heap'' in increasing order. ''Heap'' may be destroyed in the process.59 Returns a newly allocated list containing the members of ''heap'' in increasing order. ''Heap'' may be destroyed in the process. 62 60 63 61 `(list>heap `''<''` `''list''`)` 64 62 65 Constructs and returns a newheap containing the elements of ''list'' and using ''<'' as the ordering procedure. This operation should be O(n) in the size of the heap.63 Returns 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. 66 64 67 65 `(heap>vector `''heap''`)` 68 66 69 Constructs and returns a newvector containing the elements of ''heap'' in arbitrary order.67 Returns a newly allocated vector containing the elements of ''heap'' in arbitrary order. 70 68 71 69 `(heap>sortedvector! `''<''` `''heap''`)` 72 70 73 Returns a vector containing the elements of ''heap'' in increasing order. ''Heap'' may be destroyed in the process.71 Returns a newly allocated vector containing the elements of ''heap'' in increasing order. ''Heap'' may be destroyed in the process. 74 72 75 73 `(vector>heap `''<''` `''vector''`)` 76 74 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 75 Returns 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.