HeapIndex

Heaps are indexed by the same scheme as trees. Functions which process the indices only are imported and reexported from TreeIndex.

Signature of HeapIndex

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

SIGNATURE HeapIndex[data, <]

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

IMPORT Heap[data, <] ONLY heap
       Nat ONLY nat
       Option[data] ONLY option
       Option[heap] ONLY option

Parameter

SORT data
FUN < : data ** data -> bool

Handling Indices

Functions for handling indices are located in the structure IndexingOfTrees.

If the index points to root, nothing happens. Otherwise, returns the left or right subheap according to index, and adjusts the index by unleft or unright.

FUN step: heap ** nat -> heap ** nat

Accessing Values by Indices

! returns the value of the subtree with the given index, which must exist. !? returns nil, if the index does not exist.

FUN ! : heap ** nat -> data
FUN !? : heap ** nat -> option[data]

upd replace the value at the given index (which must exist) either by the given data or by result of applying the function to the old value.

FUN upd: nat ** data ** heap -> heap
FUN upd: nat ** (data -> data) ** heap -> heap

Accessing Heaps by Indices

These functions return the subheaps instead of the values of the subheaps

FUN ! : heap ** nat -> heap
FUN !? : heap ** nat -> option[heap]

repl(t,idx,new) replaces the subheap at index idx with the new heap. insert does the same, but aborts if the index does not point to an empty heap. delete replaces the subheap by an empty heap. All functions abort, if the index does not exist or the result violates the heap condition.

repl(t, idx, fct) replaces the subheap at position idx with f(idx).

FUN repl: heap ** nat ** heap -> heap
FUN repl: heap ** nat ** (heap -> heap) -> heap
FUN insert: heap ** nat ** heap -> heap
FUN delete: heap ** nat -> heap

next node: HeapReduce,
prev node: HeapFilter,
up to node: Subsystem Heaps