Title: Theory / Unimportant / CS / Algo / Purely Functional Data Structures+10
Tags: hasNotNewEffectReturnsMeaning fromAlgorithm fromMath mathToDef fromImplementation oldAlgoNewName computer_to_instruction some_instruction data_structure FromInstruction algoToProg instructionToImplementation effectToImplementation algorithm effectNew typeToSuperType algoToProblem hasSeenConjDef algoToDef declaration fromMathToDo some_instructionn

Name: Persistent data structure
Definition: A data structure which supports multiple versions.
Page: 2
Chapter: 1

Name: Ephemeral data structure
Definition: A data structure which does not support multiple versions.
Page: 2
Chapter: 1

Name: A strict language
Definition: A language in which arguments are evaluated before the body of the function.
Page: 2
Chapter: 1

Name: A lazy language
Definition: A language in which
Page: 2
Chapter: 1

Name: A lazy call
Definition: A function call in which arguments are not evaluated but are passed literally (with a context to evaluate them if required)
Page: 2
Chapter: 1

Name: Memoization
Definition: Caching the value of a term, in order to avoid computing this value a second time.
Page: 3
Chapter: 1
Section: 2

Name: Abstract data type
Definition: A type, and a collection of functions on that type.
Page: 3
Chapter: 1
Name2: An abstraction

Name: A concrete realization of \(A\)
Definition: A concrete design of \(A\).
Page: 3
Chapter: 1
Variables: \(A\) an abstract data type
Name2: An implementation of \(A\)

Name: An object
Definition: An instance of a data type.
Page: 3
Chapter: 1
Context: Purely functional data structure
Name2: A version

Name: The persistent identity of an object
Definition: The different versions of the same object through time.
Page: 3
Chapter: 1

Page: 11
Language: ocaml
Chapter: 2
Implementation: type 'a t =
  | Leaf
  | Node of {
       left :: 'a t;
       value :: 'a;
       right :: 'a t;
     }
;;
Subtype of: set
Name: Binary search trees
Assuming: 'a ordered
Invariant: The value is higher than the elements of the left subtree and lowest than the elements of the right subtrees

Name: Sharing
Definition: Different instance of a data structure may use common nodes.
A node may also appears in multiple place in the same data structure
Page: 7
Chapter: 2
Context: Data structure

Name: The right spine of \(T\)
Definition: The rightmost path from the root of \(T\) to an empty node.
Page: 18
Chapter: 3
Section: 1
Variables: \(T\) a binary tree

Name: The rank of \(T\)
Definition: The length of its right spine.
Page: 18
Chapter: 3
Section: 1
Variables: \(T\) a binary tree

Page: 17
Language: OCaml
Chapter: 3
Section: 1
Implementation: A tree whose every node is less than its children
Subtype of: heap
Name: an heap-ordered tree
Assuming: 'a ordered

Page: 18
Language: OCaml
Chapter: 3
Section: 1
Implementation: type 'a t =
  | Leaf
  | Node of
    {
      rank : int;
      value : 'a;
      left : 'a t;
      right : 'a t;
    }
;;
Subtype of: heap
Name: Leftist heap ordered tree
Assuming: 'a ordered
Invariant: leftist property: the rank of any left child is at least as large as the rank of its right sibling

Name: A tree which satisfies the weight-biased leftist property
Definition: A binary tree such that the size of any left child is at least as large as the size of its right sibling.
Page: 18
Chapter: 3
Section: 1
Name2: A leftist binary tree

Page: 21
Language: OCaml
Chapter: 3
Section: 2
Variables: \(r\in\mathbb N\)
Implementation: type 'a t =
  {
     rank : int;
     value : 'a;
     children : ('a t) list; (* contains binomial tree of rank 0, ..., r-1 exactly in this order *)
  }
;;
Name: 'a binomialTree (of rank \(r\))
Extra: Formally defined as If \(r=0\), a singleton node.
If \(r>0\), the linking of two elements of rank \(r\), making one tree the leftmost child of the other.
Invariant: Children are stored in decreasing order of their root value (a.k.a. heap ordered)

Page: 21
Language: OCaml
Chapter: 3
Section: 2
Implementation: type 'a t = ('a heapOrderedBinomialTree) list;;
Subtype of: heap
Name: A binomial heap
Assuming: 'a ordered
Invariant: Strictly increasing rank order
A tree of size \(2^i\) if there is a 1 in the \(i\)-the bit of the binary encoding of the number of elements of the heap
Potential or credit: One credit by tree

Name: Red black tree
Definition: No red node has a red child
Page: 25
Chapter: 3
Section: 2
Definition2: Empty nodes are black
Conjdef: A binary tree with a tag Red or Black
Definition3: Every path from the root to an empty node contains the same number of black nodes

Question: The depth of \(T\) is
Answer: at most \(2\log(n+1)\).
Page: 25
Chapter: 3
Section: 2
Variables: \(T\) a red-black tree with \(n\) nodes
Context: -No red node has a red child
-Every path from the root to an empty node contains the same number of black nodes
-Empty nodes are black

Name: An incremental computation
Definition: A computation which halts when enough data is produced to answer the current need.
Page: 34
Chapter: 4
Section: 2

Name: A monolithic computation
Definition: A computation which halts when the entire value is computed.
Page: 34
Chapter: 4
Section: 2

Name: The amortized cost of \(o\)
Typ: A value assigned to \(o\).
Page: 39
Section: 1
Chapter: 5
Variables: \(o\) an operation on some data

Name: The accumulated amortized cost
Definition: The sum of the amortized cost of the \(o_i\)'s.
Page: 39
Chapter: 5
Section: 1
Variables: \(o_1,\dots,o_j\) some operations

Name: The accumulated saving
Definition: The accumulated amortized cost minus their acumulated actual cost.
Page: 39
Chapter: 5
Section: 1
Variables: \(o_1,\dots,o_j\) some operations

Name: A cheap operation
Definition: An operation whose actual cost is less than its amortized cost.
Page: 40
Chapter: 5
Section: 1

Name: An expensive operation
Definition: An operation whose actual cost is greater than its amortized cost.
Page: 40
Chapter: 5
Section: 1

Name: An amortized data structure
Definition: A data structure such that, for each sequence \(o_1,\dots,o_n\) of operations, its accumulated saving is non-negative.
Page: 40
Chapter: 5
Section: 1

Name: The physicist's method
Definition: Each object is mapped to a (non-negative) real number called its potential.
Page: 41
Chapter: 5
Section: 1
Definition2: The initial object's potential is usually 0.
Conjdef: All of
Definition3: The amortized cost of an operation is its cost, plus the change in potential.

Name: A telescoping series
Definition: A series of the form \(\sum_{i=0}^n a_i-a_{i+1}\).
Page: 41
Chapter: 5
Section: 1

Question: From banker's method to physicist's method:
Answer: take the potential to be the sum of the credits.
Page: 41
Chapter: 5
Section: 1

Page: 46
Language: OCaml
Chapter: 5
Section: 4
Variables: Element, with order
Implementation: binary search tree
Name: Splay heaps
Assuming: 'a ordered
Invariant: None
Potential or credit: The credit of a node \(n\) is \(\log(\#n+1)\) where \(\#n\) is the size of the tree whose root is \(n\)

Page: 46, 47
Implementation: Returns the trees composed of the elements smaller than or equal to the pivot, and the elements greater than the pivot.
When two successive branch are taken on the same size, the tree is reordered
Section: 4
Chapter: 5
Variables: p a pivot
t a splay heap
Time complexity: Number of recursive call to pivot is:
\(1 + 2\log(n+1)+\Phi(t_<)+\Phi(t_>)-\Phi(t)\), with \(n\) the size of the tree, \(t_<\) and \(t_>\) the two output
Returns: Elements smaller than the pivot,
Elements greater than the pivot
Context: Splay heaps: binary search tree
The credit of a node \(n\) is \(\log(\#n+1)\) where \(\#n\) is the size of the tree whose root is \(n\)

Page: 43
Implementation: let rec f? ({front=front} as queue) =
  match front with
    | [] -> {front= rev queue.rear; rear=[]}
    | _ -> queue
;;
Section: 2
Chapter: 5
Effect: checkF
Language: ocaml
Time complexity: \(O(\text{number of credit})\) in the first case, spend all credits
\(O(1)\) in the second case, no credits

Page: 64
Implementation: let f? queue = match force queue.front with
  | [] -> failwith "Error"
  | head :: _ -> head
;;
Section: 3.2
Chapter: 6
Effect: head
Language: ocaml
Time complexity: \(O(1)\)
Code context: type 'a amortizedQueueWithBankerMethod =
  {
    front_size : int;
    front : 'a stream;
    rear_size : int;
    rear : 'a stream;
  };;
Front stream is at least as long than rear stream.
The number of debits on nodes from 0 to \(i\) is at most \(\min(2i,|\mathtt{front_size}|)\) and
One or two debit on each node of the front

Page: 64
Implementation: let f? queue x = {
  queue with
    rear_size = queue.rear_size+1
    rear = lazy Cons { head = x, tail = queue.rear}
}
;;
Section: 3.2
Chapter: 6
Effect: snoc
Language: ocaml
Time complexity: \(O(1)\) amortized, paying 1 debit.
Worst case \(O(lenr)\) time,
Code context: type 'a amortizedQueueWithBankerMethod =
  {
    front_size : int;
    front : 'a stream;
    rear_size : int;
    rear : 'a stream;
  };;
Front stream is at least as long than rear stream.
The number of debits on nodes from 0 to \(i\) is at most \(\min(2i,|\mathtt{front_size}|)\) and
One or two debit on each node of the front

Page: 20
Implementation: let rec f? = function
  | (Leaf, heap)
  | (heap, Leaf) -> heap
  | (Node {value = value1} as heap1,
    Node {value = value2} as heap2) ->
      let min_heap, max_heap =
        if value1 < value2
      then
        (heap1, heap2)
      else
        (heap2, heap1)
      in
        makeT(x, min_heap.left, f?(min_heap.right, max_heap))
;;
Section: 1
Chapter: 3
Effect: merge
Language: ocaml
Time complexity: \(O(\log (n))\)
Code context: type 'a leftistHeapOrderedTree =
  | Leaf
  | Node of
    {
      rank : int;
      value : 'a;
      left : 'a leftistHeapOrderedTree;
      right : 'a leftistHeapOrderedTree;
    }
;;
Both an heap-ordered and a leftist tree
makeT(value, heap1, heap2) returns a heap with content value heap1 and heap2

Page: 22
Implementation: let rec f? = function
  | t, [] -> [t]
  | t, (t'::ts' as ts) ->
    if rank t < rank t'
    then
      t::ts
    else
      f? (link, t t') ts')
Section: 2
Chapter: 3
Effect: Insert a tree
Language: ocaml
Time complexity: add one credit
Assuming \(t\)'s rank is \(n\), spend the credit associated to every successive trees of rank at least \(n\)
Code context: type 'a binomialHeap = ('a heapOrderedBinomialTree) list;;
One credit by tree
Trees in strictly increasing rank

Page: 21
Implementation: let f? (Node {rank = rank; value = value1} as heap1) (Node {value = value2} as heap2) =
      let min_heap, max_heap =
        if value1 < value2
      then
        (heap1, heap2)
      else
        (heap2, heap1)
      in
    Node {
      rank = rank + 1;
      value = min_heap.value
      children = max_heap :: min_heap.children
    }
Section: 2
Chapter: 3
Effect: Linking two trees
Language: ocaml
Time complexity: \(O(1)\)
Code context: type 'a binomialTree =
  {
     rank : int;
     value : 'a;
     children : ('a t) list; (* contains binomial tree of rank 0, ..., r-1 exactly in this order *)
  }
;;
Assuming: Both trees have the same rank

Page: 18
Implementation: let f? = fun
  | Leaft -> failwith "Empty"
  | Node node -> merge node.left node.right
Section: 1
Chapter: 3
Effect: Deleting minimal element
Language: ocaml
Time complexity: \(O(\log (n))\)
Code context: type 'a leftistHeapOrderedTree =
  | Leaf
  | Node of
    {
      rank : int;
      value : 'a;
      left : 'a leftistHeapOrderedTree;
      right : 'a leftistHeapOrderedTree;
    }
;;
Both an heap-ordered and a leftist tree

Page: 22
Implementation: fun f? ts =
  let (Node {children = children_min_heap}, heaps) = removeMinTree ts
  in
   merge (rev children_min_heap, heaps)
;;
Section: 2
Chapter: 3
Effect: Deleting minimal element
Language: ocaml
Code context: type 'a binomialHeap = ('a heapOrderedBinomialTree) list;;
One credit by tree
Trees in strictly increasing rank

Page: 25
Implementation: let f? x s=
  let fun ins = fun
     | Leaf -> Node {color = Red; left = Leaf; value = x; right = Leaf}
     | Node {color= color; left = left; value = value; right = right} as node->
       if x == value
       then node
       else let left, right =
         if x < value
         then ins left, right
         else left, ins right
      in
         Node {node with left=left; right=right}
  in
    let Node node = ins s
    in Node {node with color = Black}
               if x<y then balance (color, ins a, y, b)
;;
(*where balance replace black red red path by a path with a red, father of two black nodes*)
Section: 2
Chapter: 3
Effect: inserting an element
Variables: \(T\) a red-black tree and
\(x\) an element
Language: ocaml
Time complexity: \(O(\log n)\)
Code context: Red-black tree
-No red node has a red child
-Every path from the root to an empty node contains the same number of black nodes
-Empty nodes are black

Page: 22
Implementation: let rec f? = fun
  | [], heaps
  | heaps, [] -> heaps
  | (min_heap1 :: heaps'1) as heaps1,
    (min_heap2 :: heaps'2) as heaps2 ->
    if rank min_heap1 == rank min_heap2
    then
      insTree (link min_heap1 min_heap2) (f? heaps'1 heaps'2)
    else
      min_heaps, max_heaps =
        if rank (List.hd heaps1) < rank (List.hd heaps2)
        then
          heaps1, heaps2
        else
          heaps2, heaps1
      in
        (List.hd min_heaps) :: (f? (List.tl min_heaps) max_heaps)
;;
Section: 2
Chapter: 3
Effect: merging two heap
Language: ocaml
Time complexity: \(O(\log n)\)
Code context: type 'a binomialHeap = ('a heapOrderedBinomialTree) list;;
One credit by tree
Trees in strictly increasing rank

Page: 34
Implementation: let rec f? left right = match Lazy.force left with
  | Nil -> right
  | Cons {head=head; tail=tail} -> lazy (Cons {head=head; tail= (f? tail right)})
;;
Section: 2
Chapter: 4
Name: ++
Language: ocaml
Returns: Appending
Code context: type 'a t_aux =
  | Nil
  | Cons of {
    head : 'a;
    tail : 'a t;
  }
and
  'a t= ('a t_aux) lazy
;;

Page: 22
Implementation: let f? x ts =
  insTree (Node {rank * 0; value = x; children = []}) ts
Section: 2
Chapter: 3
Effect: Inserting an element
Language: ocaml
Code context: type 'a binomialHeap = ('a heapOrderedBinomialTree) list;;
One credit by tree
Trees in strictly increasing rank

Page: 18
Implementation: let f? value heap =
  merge
    (Node {rank = 1; value = value; left = Leaf; right = Leaf})
    h
Section: 1
Chapter: 3
Effect: Inserting an element
Language: ocaml
Code context: type 'a leftistHeapOrderedTree =
  | Leaf
  | Node of
    {
      rank : int;
      value : 'a;
      left : 'a leftistHeapOrderedTree;
      right : 'a leftistHeapOrderedTree;
    }
;;
Both an heap-ordered and a leftist tree

Page: 18
Implementation: let f? value =
  let rec aux
    | Leaf -> false
    | Node node as {value = value}->
      if value == value
      then
        true
      else
        aux (if value > value then node.left or node.right)
;;
Section: 1
Chapter: 3
Effect: member ?
Variables: \(x\) an element,
\(E\) a tree
Language: ocaml
Code context: binary search tree

Page: 22
Implementation: let rec f? = fun
  | [] -> failwith "Empty"
  | [t] -> (t,[])
  | t::ts ->
    let (t',ts')=f? ts
    in
      if root t < root t'
      then (t, ts)
      else (t', t::ts')
;;
Section: 2
Chapter: 3
Language: ocaml
Returns: The tree with minimal root, and the list of other trees,
Code context: binary heap
A list of binary trees
Instruction: removeMinTree

Page: 52
Language: OCaml
Chapter: 5
Implementation: type 'a nonEmpty =
  {
    value : 'a;
    children : 'a nonEmpty;
  };;
type 'a t =
  | Empty
  | NonEmpty of 'a nonEmpty
;;
Subtype of: 'a heap
Name: 'a pairingHeap
Assuming: 'a ordered
Invariant: value is minimal.
Children are Heap ordered

Question: Principal weakness of amortization ?
Answer: It only works with ephemeral data structures
Page: 55
Chapter: 5

Name: The execution trace of \(o\)
Definition: A directed graph whose nodes represent operations of interest, usually just update operations on the data type in question. An edge from \(v\) to \(v\) indicates that operation \(v'\) uses some result of operation \(v\).
Page: 57
Chapter: 6
Section: 1
Variables: \(o\) an object

Name: The logical history of \(v\)
Definition: The set of all operations on which the result of \(v\) depends (including \(v\) itself)
Page: 57
Chapter: 6
Section: 1
Variables: \(o\) an object,
\(v\) a node of \(o\) in its execution traces

Name: The logical future of \(v\)
Definition: Any path from the node \(v\) in an execution trace to a terminal node (i.e., a node with out-degree zero).
Page: 57
Chapter: 6
Section: 1
Variables: \(o\) an object,
\(v\) a node of \(o\) in its execution traces
Context: Data structures

Name: Its version graph
Definition: A digraph, nodes represent the various versions of a single persistent identity and edges represent dependencies between versions.
Page: 58
Chapter: 6
Section: 1
Variables: \(o\) an object,

Name: The unshared cost of \(p\)
Definition: The actual time it would take to execute \(p\) under the assumption that every suspension in the system at the beginning of the operation has already been forced and memoized (i.e., under the assumption that force always takes \(0(1)\) time, except for those suspensions that are created and forced within the same operation)
Page: 60
Chapter: 6
Section: 2.2
Variables: \(o\) an object with lazyness
\(p\) an operation on \(o\)

Name: The shared cost of \(p\)
Definition: every suspension created by \(p\)
Page: 60
Chapter: 6
Section: 2.2
Variables: \(o\) an object with lazyness
\(p\) an operation on \(o\)
Definition2: not evaluated by \(p\)
Conjdef: The time that it would take to execute
Definition3: under the assumption that force always takes \(O(1)\) time, except for those suspensions that are created and forced within the same operation

Name: Its complete cost
Definition: The sum of the shared and unshared costs of \(p\).
Page: 60
Chapter: 6
Section: 2.2
Variables: \(o\) an object with lazyness
\(p\) an operation on \(o\)

Name: The realized cost of \(p\)
Definition: The shared costs for suspensions of \(p\) that are executed during the overall computation.
Page: 60
Chapter: 6
Section: 2.2
Variables: \(o\) an object with lazyness
\(p\) an operation on \(o\)

Name: The unrealized cost of \(p\)
Definition: The shared costs for suspensions of \(p\) that are never executed.
Page: 60
Chapter: 6
Section: 2.2
Variables: \(o\) an object with lazyness
\(p\) an operation on \(o\)

Name: The total actual cost of \(p\)
Definition: The sum of unshared costs of \(p\) and the realized shared costs of \(p\)
Page: 60
Chapter: 6
Section: 2.2
Variables: \(o\) an object with lazyness
\(p\) an operation on \(o\)

Question: The amount that any \(p\) contributes to the total cost is at most
Answer: its complete cost
Page: 60
Chapter: 6
Section: 2.2
Variables: \(o\) an object with lazyness
\(p\) an operation on \(o\)

Name: The amortized cost of \(p\)
Definition: The unshared cost of \(p\) plus the amount of accumulated debt paid by \(p\)
Page: 60
Chapter: 6
Section: 2.2
Variables: \(o\) an object with lazyness
\(p\) an operation on \(o\)

Name: The debt of \(p\)
Definition: The shared cost of the suspensions in \(p\) (and any nested suspension), minus the part of the debt paid by \(p\)
Page: 60
Chapter: 6
Section: 2.2
Variables: \(o\) an object with lazyness
\(p\) an operation on \(o\)

Question: Constraint on lazyness with accumulated debt
Answer: A lazy evaluation is never forced before its debt is payd
Page: 60
Chapter: 6
Section: 2.2

Question: How to consider multiple future when analyzing lazyness with accumulated debt
Answer: Assuming that an object has an unique future
Page: 61
Chapter: 6
Section: 2.2

Page: 52
Implementation: let f? = fun
  | Empty -> failwith "Empty"
  | NonEmpty {value=value} -> value
;;
Section: 5
Effect: findMin
Language: ocaml
Time complexity: O(1) worst case
Code context: type 'a nonEmpty =
  {
    value : 'a;
    children : 'a nonEmpty;
  };;
type 'a pairingHeap =
  | Empty
  | NonEmpty of 'a nonEmpty
;;
value is minimal.
Children are Heap ordered

Page: 53
Implementation: let rec f? = fun
  | heap, Empty
  | Empty heap -> heap
  | (NonEmpty heap1), (NonEmpty heap2) ->
     let min_heap, max_heap =
       if heap1.value < heap2.value
       then
         heap1, heap2
       else
         heap2, heap1
       in
       NonEmpty {
         value=min_heap.value;
         children=max_heap :: min_heap.children;
       }
;;
Section: 5
Effect: merge
Language: ocaml
Time complexity: O(1) worst case
O(log n) amortized
Code context: type 'a nonEmpty =
  {
    value : 'a;
    children : 'a nonEmpty;
  };;
type 'a pairingHeap =
  | Empty
  | NonEmpty of 'a nonEmpty
;;
value is minimal.
Children are Heap ordered

Page: 53
Implementation: let f? value heap =
  merge (NonEmpty {value=value; children=[]}) heap
Section: 5
Effect: insert
Language: ocaml
Time complexity: O(1) worst case
O(log n) amortized
Context: value is minimal.
Children are Heap ordered
Code context: type 'a nonEmpty =
  {
    value : 'a;
    children : ('a nonEmpty) list;
  };;
type 'a pairingHeap =
  | Empty
  | NonEmpty of 'a nonEmpty
;;

Page: 53
Implementation: let f? = fun
  | Empty -> failwith "Empty"
  | NonEmpty {children=children} ->
    let rec f_aux? =
      | [] -> Empty
      | [h] -> [h]
      | [h1 :: h2 :: hs] -> merge (merge h1 h2) (mergePairs hs)
    in
  f_aux children
;;
Section: 5
Effect: deleteMin
Language: ocaml
Time complexity: O(n) worst case
O(log n) amortized
Code context: type 'a nonEmpty =
  {
    value : 'a;
    children : ('a nonEmpty) list;
  };;
type 'a pairingHeap =
  | Empty
  | NonEmpty of 'a nonEmpty
;;
value is minimal.
Children are Heap ordered

Function: efficient access to/deletion of the lowest element,
Page: 17
Name: Priority queue
Chapter: 3
Section: 1
Subtype of: A set
Name2: Heap

Function: cons (add)
Page: 8
Name: Stack
Function2: head (pop the last added element not yet removed)
Chapter: 2
Extends: Set
Section: 1
Function3: tail (everything but last added element not yet removed)
French: Pile
Name2: First-in last-out
Abbreviation: FILO

Function: add
Page: 42
Name: Set
Function2: isEmpty
Chapter: 5
Section: 1
Function3: pop: remove an element from the set and return it
French: Ensemble
Initialization: empty

Function: snoc
Page: 42
Name: First-in first-out
Function2: head
Chapter: 5
Section: 1
Function3: tail
Subtype of: A set
Function4: isEmpty
French: Pile
Initialization: empty
Name2: Queues
Abbreviation: FIFO
Extra: h

Name: The banker's method
Definition: Some credit is associated with individual locations in the data structure.
The cost of an operation is the actual cost, plus the credits allocated minus the credits spent.
Page: 40
Chapter: 5
Section: 1

Meaning: A potentially infinite sequence of elements of type 'a
Page: 34
Language: OCaml
Chapter: 4
Section: 2
Implementation: type 'a t_aux =
  | Nil
  | Cons of {
    head : 'a;
    tail : 'a t;
  }
and
  'a t= ('a t_aux) lazy
;;
Name: 'a stream

Page: 64
Language: OCaml
Chapter: 6
Section: 3.2
Implementation: type 'a t =
  {
    front_size : int;
    front : 'a stream;
    rear_size : int;
    rear : 'a stream;
  };;
Subtype of: 'a queue
Name: Amortized queue with Banker method
Invariant: Front stream is at least as long than rear stream.
The number of debits on nodes from 0 to \(i\) is at most \(\min(2i,|\mathtt{front_size}|)\) and
Potential or credit: One or two debit on each node of the front
Code context: type 'a t_aux =
  | Nil
  | Cons of {
    head : 'a;
    tail : 'a t;
  }
and
  'a t= ('a t_aux) lazy
;;

Meaning: represents front followed by reversed rear
Page: 42
Language: OCaml
Chapter: 5
Section: 2
Implementation: type 'a t = {
  front : 'a list;
  rear : 'a list;
}
Subtype of: 'a queue
Name: 'a batchedQueue
Invariant: left is empty implies right is empty.
Potential or credit: One credit on each element of the right list

Page: 43
Implementation: let f? ({front=front} as queue) =
  match force front with
    | [] -> faiwith "Empty"
    | head :: front_tail -> checkf {queue with front = lazy front_tail; front_size = queue.front_size -1}
;;
Section: 2
Chapter: 5
Effect: tail
Language: ocaml
Time complexity: 1, and no credit amortized
\(|r|\) worst case
Code context: type 'a amortizedQueueWithBankerMethod =
  {
    front_size : int;
    front : 'a stream;
    rear_size : int;
    rear : 'a stream;
  };;

Page: 64
Implementation: let f? queue = match force queue.front with
  | [] -> failwith "Error"
  | _ :: front' ->
    check {queue with
        front_size = queue.front_size - 1;
        front = lazy front';
      }
;;
Section: 3.2
Chapter: 6
Effect: tail
Language: ocaml
Time complexity: \(O(1)\) amortized, paying 2 debit.
Worst case \(O(lenr)\) time,
Code context: type 'a amortizedQueueWithBankerMethod =
  {
    front_size : int;
    front : 'a stream;
    rear_size : int;
    rear : 'a stream;
  };;
Front stream is at least as long than rear stream.
The number of debits on nodes from 0 to \(i\) is at most \(\min(2i,|\mathtt{front_size}|)\) and
One or two debit on each node of the front

Page: 64
Implementation: let f? queue =
  if queue.rear_size <= queue.front_size
  then
    queue
  else
    {
       front_size = queue.front_size + queue.rear_size;
       front = queue.front ++ (reverse queue.rear);
       rear_size = 0
       rear = lazy Empty
    }
;;
Section: 3.2
Chapter: 6
Name: check
Language: ocaml
Time complexity: \(O(1)\) amortized, discharing \(lenr\) debits
worst case \(lenr\)
Returns: A queue equivalent to the input, with front as least as long as rear
Code context: type 'a amortizedQueueWithBankerMethod =
  {
    front_size : int;
    front : 'a stream;
    rear_size : int;
    rear : 'a stream;
  };;

Name: A debit
Definition: A value, associated with some node of a data structure
Page: 61
Chapter: 6
Section: 3

Name: Banker with debit method
Definition: Associating to suspended nodes some debits. Those debits should be discarded before the content of those nodes are accessed.
Page: 61
Chapter: 6
Section: 3

Name: A suspension \(s\) which depends of another suspension \(s'\)
Definition: A suspension \(s\) whose creation requires to force a suspension \(s'\).
Page: 67
Chapter: 6
Section: 3

Question: What is the requirement with banker's method concerning depending supsensions ?
Answer: The outer suspension can be forced only when the inner suspension can also be called.
Page: 67
Chapter: 6
Section: 3

Question: What happen to the debit of \(s'\) when \(s\) is created ?
Answer: \(s\) inherit \(s'\)'s debit.
Page: 67
Chapter: 6
Section: 3
Variables: \(s,s'\) suspensions.
\(s\) depends of \(s'\)
Assuming: There is no way, apart from \(s\), to access \(s'\)

Name: Debit inheritance
Definition: The fact that, each unpayed debit of \(s'\) goes to \(s\) when \(s\) is created.
Page: 67
Chapter: 6
Section: 3
Variables: \(s,s'\) suspensions.
\(s\) depends of \(s'\)
Assuming: There is no way, apart from \(s\), to access \(s'\)

Question: Difference between debts and credits in banker's method ?
Answer: Credit must be paid before the code is executed.
Debit can be paid after execution of the code, assuming they are in suspensions. Suspensions can't be forced until their debts are paid.
Page: 61
Chapter: 6
Section: 3

Question: For monolitic suspensions, which method to use ?
Answer: Physicists
Page: 70
Chapter: 6
Section: 4

Meaning: A heap whose minimal element is the root of one the tree
Page: 70
Language: OCaml
Chapter: 6
Section: 4.1
Implementation: (('a binomialHeap) list) lazy
Subtype of: 'a heap
Name: 'a lazyBinomialHeap
Potential or credit: Potential: number of 0 in the binary representation of the number of elements.

Page: 74
Name: A sortable collection
Chapter: 6
Section: 4.3
Subtype of: A set of lists
Intuition: The part in common can be sorted once in order to sort every list without doing twice similar work
Invariant: when some lists share common tails, this fact can be used to sort those lists efficiently.

Question: The rank of \(T\) is
Answer: at most \(\log (n+1)\).
Page: 18
Chapter: 3
Section: 1
Variables: \(T\) a leftist binary tree with \(n\) elements
Context: Invariant:
-Every left child's rank is at least as large as the rank of its right sibling

Question: The amount that any \(p\) contributes to the total cost is at least
Answer: its unshared cost.
Page: 60
Chapter: 6
Section: 2.2
Variables: \(o\) an object with lazyness
\(p\) an operation on \(o\)

Name: The complete cost of \(p\).
Definition: The sum of the shared and unshared costs of \(p\).
Page: 60
Chapter: 6
Section: 2.2
Variables: \(o\) an object with lazyness
\(p\) an operation on \(o\)

Instruction: empty
Page: 8
Language: ocaml
Context: Some set module
Chapter: 2
Section: 1
Returns: An empty object
Extra: prog
Typ: \(\alpha\) objectType

Instruction: isEmpty s
Page: 8
Language: ocaml
Chapter: 2
Section: 1
Returns: Whether a stack is empty
Extra: prog
Typ: 'a stack -> bool

Instruction: cons
Page: 8
Effect: take a head, a stack
Language: ocaml
Chapter: 2
Section: 1
Returns: a new stack with the head as first element and then the old stack
Extra: prog
Typ: 'a -> 'a stack -> 'a stack

Instruction: Head
Page: 8
Language: ocaml
Chapter: 2
Section: 1
Returns: The first element of a stack.
Extra: prog
Typ: 'a stack -> 'a
Exception: Empty if stack is empty

Instruction: Tail
Page: 8
Language: ocaml
Chapter: 2
Section: 1
Returns: The stack without its first element.
Extra: prog
Typ: 'a stack -> 'a stack
Exception: Empty if stack is empty

Instruction: ++
Page: 8
Effect: Takes as input two stacks
Language: ocaml
Chapter: 2
Section: 1
Returns: a new stack starting with the first input, followed by the second one
Extra: prog
Typ: 'a stack x 'a stack -> 'a stack

Instruction: insert elt set
Page: 12
Language: ocaml
Chapter: 2
Returns: a new set containing exactly the set \(set\cup \{elt\}\)
Extra: prog
Typ: element x Set -> Set

Instruction: member
Page: 12
Effect: Takes as input an element, a set, and accepts if the elements belong to the set
Language: ocaml
Chapter: 2
Extra: prog
Typ: element x Set -> bool

Instruction: merge set1 set2
Page: prog
17
Language: ocaml
Chapter: 3
Section: 1
Returns: a new set containing exactly the elements of the two inputs.
Extra: prog
Typ: Heap x Heap -> Heap

Instruction: findMin heap
Page: 17
Language: ocaml
Context: Heap
Chapter: 3
Section: 1
Returns: minimal element of heap if it exists
Extra: prog
Typ: Heap -> Element.T
Exception: Empty if the heap is empty

Instruction: $e
Page: prog
31
Effect: An expression, whose value is the same than the value of e, which is computed only when this value is explictly used in a pattern matching
Language: ocaml
Chapter: 4
Section: 1
Variables: e of type t
Extra: prog
Typ: t susp

Instruction: force ($x)
Page: prog
32
Effect: The value of $x
Language: ocaml
Chapter: 4
Section: 1
Variables: x : t susp
Extra: prog
Typ: t

Instruction: fun lazy functionName args = expr
Page: prog
33
Meaning: Syntactic sugar for:
fun functionName args' =
$case args' of args => force expr
Language: ocaml
Chapter: 4
Section: 1
Typ: $typeOfArgs => $expr
Extra: prog

Page: 42
Effect: Add an element at the end of the queue
Language: ocaml
Chapter: 5
Section: 1
Extra: Problem
Typ: 'a Queue -> 'a -> 'a queue
Name: snoc

Page: 43
Implementation: let f? = fun
  | {front=[]}  -> true
  | {front = _} -> false
;;
Section: 2
Chapter: 5
Effect: isEmpty?
Language: ocaml
Code context: Heap

Page: 43
Effect: Transform a queue into an equivalent queue which satisfies the invariant
Language: ocaml
Context: \(\alpha\) Queue
\(\alpha\) list X \(\alpha\) list
left is empty implies right is empty. One credit on each element of the right list
Chapter: 5
Section: 2
Extra: Problem
Name: checkF

Question: The number of nodes of a binomial tree of rank \(r\) is
Answer: \(2^r\).
Page: 21
Chapter: 3
Section: 2
Variables: \(r\in\mathbb N\)

Question: When would one prefer to consider worst-case over average case
Answer: Real-time system
Page: 83
Chapter: 7
Answer2: Parallel system
Answer3: Interactive system
Answer4: Persistent data structure

Name: The intrinsic cost of \(s\)
Definition: The cost of executing \(s\), assuming each suspension inside is already memoized
Page: 84
Chapter: 7
Section: 1
Variables: \(s\) a suspension

Question: Cost of \((\dots((s_1++s_2)++s_2)++\dots)++s_k\)
Answer: \(O(k)\)
Page: 85
Chapter: 7
Section: 1
Variables: \(s_1,\dots,s_k\) executed suspensions

Question: The steps of converting amortized data structure to a worst-case data structure
Answer: Reduce intrinsic cost of every suspension to less than the desired bounds
Page: 84, 85
Chapter: 7
Section: 1
Variables: \(s_1,\dots,s_k\) executed suspensions
Answer2: Dealing with nested suspensions

Name: Scheduling
Definition: Ensuring that, when a debt is paid, it corresponds to the execution of some computation
Page: 84, 85
Chapter: 7
Section: 1
Context: Functional data structure
Extra: algoToDef

Name: A schedule
Definition: A set of pointers to every unevaluated suspensions in the object
Page: 84, 85
Chapter: 7
Section: 1
Variables: \(d\) an object with suspensions

Meaning: represents front followed by reversed rear
Page: 87
Language: OCaml
Chapter: 7
Section: 2
Implementation: 'a t = {
  stream_front : 'a stream;
  rear : 'a list;
  stream_schedule : 'a stream
}
Subtype of: 'a batchedQueue
Name: Real-time queue
Invariant: \(|\mathtt{schedule}|=|\mathtt{front}|-|\mathtt{rear}|\)
schedule is a suffix of front
Code context: type 'a stream_aux =
  | Nil
  | Cons of {
    value : 'a;
    s : 'a stream;
  }
and
  'a stream= ('a stream_aux) lazy
;;

Page: 86
Implementation: let rec list1 list2 list3 = match (Lazy.force list1, Lazy.force list2) with
  | [], [h] -> lazy h :: list3
  | h1::t1, h2::t2 ->
    lazy (
      x :: rotate t1 t2 (lazy h2 :: list3)
    )
;;
Section: 2
Chapter: 7
Name: rotate
Language: ocaml
Time complexity: Intrinsic cost O(1)
Returns: takes three list, append them with the middle one reversed
Assuming: \(|list2|=|list1|+1\)
Extra: list3 is NOT the scheduler but an accumulator

Page: 87
Implementation: let f? queue value =
  exec {
    queue with
    stream_rear = lazy (
      Cons {
        hd = value;
        tl = queue.stream_rear;
      }
    )
  }
;;
Section: 2
Chapter: 7
Name: snoc
Language: ocaml
Time complexity: Worst-case \(O(1)\)
Context: \(|\mathtt{schedule}|=|\mathtt{front}|-|\mathtt{rear}|\)
Code context: 'a realTimeQueue = {
  stream_front : 'a stream;
  rear : 'a list;
  stream_schedule : 'a stream
}

Page: 87
Implementation: let f? queue =
  List.hd (force queue.front)
;;
Section: 2
Chapter: 7
Name: head
Language: ocaml
Time complexity: Worst-case \(O(1)\)
Context: \(|\mathtt{schedule}|=|\mathtt{front}|-|\mathtt{rear}|\)
Code context: 'a realTimeQueue = {
  stream_front : 'a stream;
  rear : 'a list;
  stream_schedule : 'a stream
}

Page: 87
Implementation: let f? queue =
  List.tl (force queue.stream_front)
;;
Section: 2
Chapter: 7
Name: tail
Language: ocaml
Time complexity: Worst-case \(O(1)\)
Context: \(|\mathtt{schedule}|=|\mathtt{front}|-|\mathtt{rear}|\)
Code context: 'a realTimeQueue = {
  stream_front : 'a stream;
  rear : 'a list;
  stream_schedule : 'a stream
}

Page: 88
Implementation: let f? queue = match force queue.schedule with
  | _ :: t -> {queue with schedule = t}
  | [] ->
    let front = rotate queue in {
      stream_front = front;
      rear = [];
      stream_schedule = front
    }
;;
Section: 2
Chapter: 7
Name: exec
Language: ocaml
Time complexity: Worst-case \(O(1)\)
Returns: Execute one element of the schedule, or reverse
Context: \(|\mathtt{schedule}|=|\mathtt{front}|-|\mathtt{rear}|\)
Code context: 'a realTimeQueue = {
  stream_front : 'a stream;
  rear : 'a list;
  stream_schedule : 'a stream
}

Page: 70
Implementation: let f? value heaps =
  $insTree (Node {rank=0; value=x; children=[]}) heaps
;;
Section: 4.1
Chapter: 6
Effect: insert
Language: ocaml
Time complexity: Amortized \(O(1)\)
Code context: 'a lazyBinomialHeap = 'a binomialHeap list lazy;;

Page: 71
Implementation: let f? heap1 heap2 =
  let min_heap, max_heap =
    if heap1.value < heap2.value
    then heap1, heap2
    else heap2, heap1
  in
  {
    rank = heap1.rank +1;
    value = min_heap.value;
    children = max_heap :: min_heap.children
  }
;;
Section: 4.1
Chapter: 6
Effect: link
Language: ocaml
Time complexity: Amortized \(O(1)\)
Code context: type 'a binomialTree =
  {
     rank : int;
     value : 'a;
     children : ('a t) list; (* contains binomial tree of rank 0, ..., r-1 exactly in this order *)
  }
;;
Assuming: both have same degree

Page: 71
Implementation: let rec f? heap = fun
  | [] -> [heap]
  | (heaps_head :: heaps_tail) as heaps ->
    if rank heap < rank heaps_head
    then
      heap :: heaps
    else
      heaps_head :: (f? heap heaps_tail)
;;
Section: 4.1
Chapter: 6
Effect: insTree
Language: ocaml
Time complexity: Amortized \(O(1)\)
Code context: 'a lazyBinomialHeap = (('a binomialHeap) list) lazy;;

Page: 71
Implementation: let rec f? = fun
  | heaps, []
  | [], heaps -> heaps
  | (heap1 :: heaps'1) as heaps1,
    (heap2 :: heaps'2) as heaps2 ->
       let rank1 = rank heap1
       and rank2 = rank heap2 in
       if rank1 == rank2
       then
         insTre (link (heap1, heap2)) (mrg heaps'1 heaps'2)
       else
         min_heap, min_heaps', max_heaps =
           if rank1 < rank2
           then (heap1, heaps'1, heaps2)
           else (heap2, heaps'2, heaps1)
         in
           min_heap :: f? min_heaps' max_heaps
;;
Section: 4.1
Chapter: 6
Effect: mrg
Language: ocaml
Time complexity: Amortized \(O(1)\)
Code context: 'a lazyBinomialHeap = 'a binomialHeap list lazy;;

Page: 71
Implementation: let f? heaps1 heaps2 =
  lazy $mrg (Lazy.force heaps1) (Lazy.force heaps2)
Section: 4.1
Chapter: 6
Effect: Merge
Language: ocaml
Time complexity: Amortized \(O(1)\)
Code context: 'a lazyBinomialHeap = 'a binomialHeap list lazy;;

Page: 71
Implementation: let rec f? = fun
  | [] -> failwith "Empty"
  | [heap] -> (heap, [])
  | first_heap :: heaps ->
     let (min_remaining_tree, other_trees) = f? heaps in
     if root first_heap < root min_remaining_tree
     then
       (first_heap, heaps)
     else
       (min_remaining_tree, first_heap :: other_trees)
;;
Section: 4.1
Chapter: 6
Effect: removeMinTree
Language: ocaml
Time complexity: Amortized \(O(1)\)
Code context: 'a lazyBinomialHeap = 'a binomialHeap list lazy;;

Page: 71
Implementation: let f? heaps =
  let min_tree, _ = removeMinTree (force heaps) in
  root min_tree
;;
Section: 4.1
Chapter: 6
Effect: findMin
Language: ocaml
Time complexity: Amortized \(O(1)\)
Code context: 'a lazyBinomialHeap = 'a binomialHeap list lazy;;

Page: 71
Implementation: let f? heaps =
  List.null (Lazy.force heaps)
Section: 4.1
Chapter: 6
Effect: isEmpty
Language: ocaml
Time complexity: Amortized \(O(1)\)
Worst case \(O(\log n)\)
Code context: 'a lazyBinomialHeap = 'a binomialHeap list lazy;;

Page: 72
Language: OCaml
Chapter: 6
Section: 4.1
Implementation: type 'a t = {
  working_copy :: 't list,
  len_front :: Int,
  lazy_front :: 't list susp,
  len_rear :: int,
  rear :: 't list,
}
Subtype of: 'a batchedQueue
Name: 'a PhysicistsQueue
Invariant: len_x is the length of x
working_copy is a prefix of front
if front is non empty then working_copy is non empty
\(|\mathtt{front}|\ge|\mathtt{rear}|\)
Potential or credit: Potential is [$]\min(2\abs{\mathtt{working\_copy}},\abs{\mathtt{front}}-\abs{\mathtt{rear}})[/$]
Code context: type 'a stream_aux =
  | Nil
  | Cons of {
    value : 'a;
    s : 'a stream;
  }
and
  'a stream= ('a stream_aux) lazy
;;

Page: 72
Implementation: let f? queue value = {
  queue with
  len_rear = queue.len_rear + 1;
  rear = value :: queue.rear;
}
;;
Section: 4.1
Chapter: 6
Name: snoc
Language: ocaml
Time complexity: \(O(1)\) amortized, paying 1 debit.
Worst case \(O(lenr)\) time,
Code context: type 'a physicistQueue = {
  working_copy :: 't list,
  len_front :: Int,
  lazy_front :: 't list susp,
  len_rear :: int,
  rear :: 't list,
}

Page: 72
Implementation: let f? = fun
  | { working_copy = []} -> failwith "Error"
  | { working_copy = head :: _} -> head
;;
Section: 4.1
Chapter: 6
Variables: \(\alpha\) a type
Name: head
Language: ocaml
Code context: type 'a physicistQueue = {
  working_copy :: 't list,
  len_front :: Int,
  lazy_front :: 't list susp,
  len_rear :: int,
  rear :: 't list,
}

Page: 72
Implementation: let f? = fun
  | { working_copy = []} -> failwith "Empty"
  | {working_copy = working_head :: working_tail} as queue -> check {
      queue with
      working_copy = working_tail;
      len_front = que.len_front - 1;
      lazy_front = lazy (List.tl (force queue.front))
    }
;;
Section: 4.1
Chapter: 6
Name: tail
Language: ocaml
Time complexity: Amortized \(O(1)\)
Code context: type 'a physicistQueue = {
  working_copy :: 't list,
  len_front :: Int,
  lazy_front :: 't list susp,
  len_rear :: int,
  rear :: 't list,
}

Page: 72
Implementation: let f? = fun
  | {working_copy = [], lazy_front = lazy_front} as queue ->
      { queue with
       working_copy = force lazy_front
      }
  | queue -> queue
;;
Section: 4.1
Chapter: 6
Name: checkw
Language: ocaml
Returns: Repare the structure to have non-empty front
Code context: type 'a physicistQueue = {
  working_copy :: 't list,
  len_front :: Int,
  lazy_front :: 't list susp,
  len_rear :: int,
  rear :: 't list,
}

Page: 72
Implementation: let f? queue =
   if queue.len_rear < queue.len_front
   then
     checkw queue
   else
     let front = force queue.lazy_front in
     checkw {
       working_copy = front;
       len_front = queue.len_front + queue.len_rear;
       front = lazy (front @ rev queue.rear);
       len_rear = 0;
       rear = []
     }
;;
Section: 4.1
Chapter: 6
Variables: 'a comparable
Name: check
Language: Haskell
Returns: Repare the structure so that it satisfies the invariant
Code context: type 'a physicistQueue = {
  working_copy :: 't list,
  len_front :: Int,
  lazy_front :: 't list susp,
  len_rear :: int,
  rear :: 't list,
}

Page: 75
Language: OCaml
Chapter: 6
Section: 4.3
Variables: 'a ordered
Implementation: type 'a t = {
  size: int;
  segments: 'a list list lazy (* increasing size of list; increasing elements in each list *)
}
Name: 'a Sortable
Invariant: size: total size of the collection
segments: list in increasing order of size
segments' element: list in increasing order
One list of size \(2^i\) for each \(i\) such that the \(i\)-th bit of size is 1
Potential or credit: Physicist method:
\(2n-2\sum_{i=0}^\infty b_i((n\mod 2^i)+1)\) with \(b_i\) the \(i\)-th bit of \(n\)
Code context: type 'a stream_aux =
  | Nil
  | Cons of {
    value : 'a;
    s : 'a stream;
  }
and
  'a stream= ('a stream_aux) lazy
;;

Page: 75
Implementation: let rec f? = fun
  | [], l
  | l, [] -> l
  | (h1 :: t1) as l1, (h2 :: t2) as l2 ->
    let min_head, min_tail, max_list =
    if h1 < h2
    then
      h1, t1, l2
    else
      h2, t2, l1
    in
    min_head :: f? min_tail max_list
;;
Section: 4.3
Chapter: 6
Variables: Elem an ordered type
Name: mrg
Language: ocaml
Returns: Sorted list whose content is union of input
Input: Two sorted lists

Page: 75
Implementation: let rec f? segment {segments = segments; size = size} =
  if size mod 2 == 0
  then
    segment :: segments
  else
    f?
      (mrg segment (List.hd segments))
      {segments = List.tl segments; size = size / 2; }
;;
Section: 4.3
Chapter: 6
Variables: 'a sorted
Name: addSeg
Language: ocaml
Time complexity: \(O(\log n)\) amortized
Returns: A sortable which is the union of inputs
Context: size: total size of the collection
segments: list in increasing order of size
segments' element: list in increasing order
One list of size \(2^i\) for each \(i\) such that the \(i\)-th bit of size is 1
Code context: type 'a Sortable = {
  size: int;
  segments: 'a list list lazy (* increasing size of list; increasing elements in each list *)
}
Input: A segment of size power of 2
A sortable

Page: 75
Implementation: let rec f? segment =
  | fun [] -> segment
  | fun (segment', segments) ->
    f? (mrg segment segment') segments
;;
Section: 4.3
Chapter: 6
Variables: 'a sorted
Name: mrgAll
Language: ocaml
Time complexity: \(O(n)\) amortized
Returns: A list, with all content of the sortable, sorted
Context: size: total size of the collection
segments: list in increasing order of size
segments' element: list in increasing order
One list of size \(2^i\) for each \(i\) such that the \(i\)-th bit of size is 1
Code context: type 'a Sortable = {
  size: int;
  segments: 'a list list lazy (* increasing size of list; increasing elements in each list *)
}

Page: 80
Implementation: let f? = fun
  | Leaf, n
  | n, Leaf -> n
  | Node ({min = min1} as node1),
    Node ({min = min2} as node2) ->
  let min_node, max_node =
    if min1 < min2
    then
      node1, node2
    else
      node2, node1
    in
    link min_node max_node
;;
Section: 4.3
Chapter: 6
Variables: Elem an ordered type
Name: merge
Language: ocaml
Code context: 'a lazyPairingHeap =
  | Leaf
  | Node of {
    min : 'a;
    heap1 : 'a Heap;
    lazy_heap2 : 'a Heap lazy;
  }
;;

Page: 80
Implementation: let f? = fun
  | Leaf -> failwith "Empty"
  | Node {heap1 = heap1; heap2 = heap2} ->
    merge heap1 (force heap2)
;;
Section: 4.3
Chapter: 6
Effect: deleteMin
Variables: Elem an ordered type
Language: ocaml
Code context: 'a lazyPairingHeap =
  | Leaf
  | Node of {
    min : 'a;
    heap1 : 'a Heap;
    heap2 : 'a Heap lazy;
  }
;;

Page: 8
Implementation: type 'a t =
  | Nil
  | Const of ('a * 'a t)
;;
Subtype of: 'a stack
Name: 'a list
Code context: coq

Page: 20
Implementation: let f? (x, heap_left, heap_right) =
  let min_heap, max_heap =
    if rank heap_left >= rank heap_right
  then
    (heap_right, heap_left)
  else
    (heap_left, hear_right)
  in
    Node {rank = (rank max_heap) +1; value = x; left = min_heap; right = max_heap}
;;
Section: 1
Chapter: 3
Time complexity: O(1)
Returns: a heap with content of value, heap1 and heap2
Code context: type 'a leftistHeapOrderedTree =
  | Leaf
  | Node of
    {
      rank : int;
      value : 'a;
      left : 'a leftistHeapOrderedTree;
      right : 'a leftistHeapOrderedTree;
    }
;;
Both an heap-ordered and a leftist tree
Instruction: makeT
Assuming: value is minimal
Input: value: 'a
heap1, heap2: 'a leftistHeapOrderedTree

Page: 20
Implementation: let f? =  function
  | Leaf -> 0
  | Node node -> node.rank
;;
Section: 1
Chapter: 3
Time complexity: O(1)
Code context: type 'a leftistHeapOrderedTree =
  | Leaf
  | Node of
    {
      rank : int;
      value : 'a;
      left : 'a leftistHeapOrderedTree;
      right : 'a leftistHeapOrderedTree;
    }
;;
Both an heap-ordered and a leftist tree
Instruction: rank

Page: 77
Implementation: let rec f? value segments =
  {
    size = segments.size + 1;
    segments = $addSeg [value] segments
  }
Section: 4.3
Chapter: 6
Variables: 'a sorted
Language: ocaml
Context: size: total size of the collection
segments: list in increasing order of size
segments' element: list in increasing order
One list of size \(2^i\) for each \(i\) such that the \(i\)-th bit of size is 1
Code context: type 'a Sortable = {
  size: int;
  segments: 'a list list lazy (* increasing size of list; increasing elements in each list *)
}
Instruction: add

Typ: LazyPairingHeap
Meaning: standard heap, with one child suspended
Page: 80
Language: ocaml
Chapter: 6
Section: 4.3
Variables: 'a sorted
Implementation: 'a t? =
  | Leaf
  | Node of {
    min : 'a;
    heap1 : 'a Heap;
    lazy_heap2 : 'a Heap lazy;
  }
;;

Page: 71
Language: ocaml
Chapter: 6
Section: 4.1
Implementation: let f? (lazy_heaps) =
  lazy (
    let (Node {children = children_of_min}, not_min_heaps) = removeMinTree (force lazy_heaps) in
    $mrg (rev children_of_min) not_min_heaps
  )
;;
Name: 'a lazyBinomialHeap = (('a binomialHeap) list) lazy;;
Extra: prog
Example: Amortized \(O(1)\)
Code context: 'a lazyBinomialHeap = 'a binomialHeap list lazy;;