basis/heaps/heaps-docs.factor

   1 USING: heaps.private help.markup help.syntax kernel math assocs
   2 math.order ;
   3 IN: heaps
   4
   5 ARTICLE: "heaps" "Heaps"
   6 "A heap is an implementation of a " { $emphasis "priority queue" } ", which is a structure that maintains a sorted set of elements. The key property is that insertion of an arbitrary element and removal of the first element (determined by order) is performed in O(log n) time."
   7 $nl
   8 "Heap elements are key/value pairs and are compared using the " { $link <=> } " generic word on the first element of the pair."
   9 $nl
  10 "There are two classes of heaps. Min-heaps sort their elements so that the minimum element is first:"
  11 { $subsection min-heap }
  12 { $subsection min-heap? }
  13 { $subsection <min-heap> }
  14 "Max-heaps sort their elements so that the maximum element is first:"
  15 { $subsection max-heap }
  16 { $subsection max-heap? }
  17 { $subsection <max-heap> }
  18 "Both obey a protocol."
  19 $nl
  20 "Queries:"
  21 { $subsection heap-empty? }
  22 { $subsection heap-size }
  23 { $subsection heap-peek }
  24 "Insertion:"
  25 { $subsection heap-push }
  26 { $subsection heap-push* }
  27 { $subsection heap-push-all }
  28 "Removal:"
  29 { $subsection heap-pop* }
  30 { $subsection heap-pop }
  31 { $subsection heap-delete } ;
  32
  33 ABOUT: "heaps"
  34
  35 HELP: <min-heap>
  36 { $values { "min-heap" min-heap } }
  37 { $description "Create a new " { $link min-heap } "." } ;
  38
  39 HELP: <max-heap>
  40 { $values { "max-heap" max-heap } }
  41 { $description "Create a new " { $link max-heap } "." } ;
  42
  43 HELP: heap-push
  44 { $values { "key" "a comparable object" } { "value" object } { "heap" "a heap" } }
  45 { $description "Push a pair onto a heap. The key must be comparable with all other keys by the " { $link <=> } " generic word." }
  46 { $side-effects "heap" } ;
  47
  48 HELP: heap-push*
  49 { $values { "key" "a comparable object" } { "value" object } { "heap" "a heap" } { "entry" entry } }
  50 { $description "Push a pair onto a heap, and output an entry which may later be passed to " { $link heap-delete } "." }
  51 { $side-effects "heap" } ;
  52
  53 HELP: heap-push-all
  54 { $values { "assoc" assoc } { "heap" "a heap" } }
  55 { $description "Push every key/value pair of an assoc onto a heap." }
  56 { $side-effects "heap" } ;
  57
  58 HELP: heap-peek
  59 { $values { "heap" "a heap" } { "key" object } { "value" object } }
  60 { $description "Output the first element in the heap, leaving it in the heap." } ;
  61
  62 HELP: heap-pop*
  63 { $values { "heap" "a heap" } }
  64 { $description "Remove the first element from the heap." }
  65 { $side-effects "heap" } ;
  66
  67 HELP: heap-pop
  68 { $values { "heap" "a heap" } { "key" object } { "value" object } }
  69 { $description "Output and remove the first element in the heap." }
  70 { $side-effects "heap" } ;
  71
  72 HELP: heap-empty?
  73 { $values { "heap" "a heap" } { "?" "a boolean" } }
  74 { $description "Tests if a heap has no nodes." } ;
  75
  76 HELP: heap-size
  77 { $values { "heap" "a heap" } { "n" integer } }
  78 { $description "Returns the number of key/value pairs in the heap." } ;
  79
  80 HELP: heap-delete
  81 { $values { "entry" entry } { "heap" "a heap" } }
  82 { $description "Remove the specified entry from the heap." }
  83 { $errors "Throws an error if the entry is from another heap or if it has already been deleted." }
  84 { $side-effects "heap" } ;