HeapReduce

Reduce the elements of a heap by a combining function to a single value.

Signature of HeapReduce

List of Import References :
See BOOL
See DENOTATION
See Heap
See Nat
See Option
See Seq
See Tree

 SIGNATURE HeapReduce[from, < : from ** from -> bool, to]

$Date: 2010-09-30 18:24:17 +0200 (Do, 30. Sep 2010) $ ($Revision: 616 $)

IMPORT Heap[from, <] ONLY heap

Parameter

from is the data type of the elements of the heap, from is the result type of the combining function.

SORT from to
FUN < : from ** from -> bool

Reduce

This reduce variant combines the elements of the tree in ascending order.

FUN / : (from ** to -> to) ** to ** heap[from, <] -> to

The functions takes the root value and the result of reducing the left and right subheaps respectively. The initial to value is returned for the empty heap.

FUN / :  (from ** to ** to -> to) ** to ** heap[from, <] -> to

The following functions are more similar to the reduce function on sequences, as the function takes one from and one to value. For remembering the names, keep in mind that (::, <>) /_order t constructs are order traversal of the tree, where order is one of { in, pre or post.

FUN /_pre /_in /_post: (from ** to -> to) ** to ** heap[from, <] -> to

next node: HeapMap,
prev node: HeapIndex,
up to node: Subsystem Heaps