H

| < Day Day Up > |

# Index

### H

half 3-CNF satisfiability, 1018 ex.
HALF-CLEANER, 713
half-open interval, 311
Hall's theorem, 669 ex.
halting problem, 966
halving lemma, 832
HAM-CYCLE, 979
hamiltonian cycle, 967, 979
hamiltonian-cycle problem, 979, 1008- 1012
hamiltonian graph, 979
hamiltonian path, 983 ex.
hamiltonian-path problem, 1017 ex.
HAM-PATH, 983 ex.
handle, 139, 456, 477
handshaking lemma, 1084 ex.
harmonic number, 1060
harmonic series, 1060
HASH-DELETE, 244 ex.
hash function, 224, 229- 237
auxiliary, 239
division method for, 230- 231
∈-universal, 236 ex.
multiplication method for, 231- 232
one-way, 886
universal, 232- 236
hashing, 221- 252
chaining, 225- 228, 250 pr.
double, 240- 241, 244 ex.
k-universal, 251 pr.
open addressing, 237- 245
perfect, 245- 249
universal, 232- 236
HASH-INSERT, 238, 244 ex.
HASH-SEARCH, 238, 244 ex.
hash table, 224- 229
dynamic, 424 ex.
secondary, 245
see also hashing
hash value, 224
hat-check problem, 98 ex.
head
in a disk drive, 435
of a linked list, 204
of a queue, 202
heap, 127- 144
analyzed by potential method, 416 ex.
binomial, see binomial heap
building, 132- 135, 142 pr.
d-ary, 143 pr., 641 pr.
deletion from, 142 ex.
in Dijkstra's algorithm, 599
extracting the maximum key from, 139
Fibonacci, see Fibonacci heap
as garbage-collected storage, 127
height of, 129
in Huffman's algorithm, 388
to implement a mergeable heap, 455
increasing a key in, 139- 140
insertion into, 140
in Johnson's algorithm, 640
max-heap, 128
maximum key of, 139
mergeable, see mergeable heap
min-heap, 129
in Prim's algorithm, 573
as a priority queue, 138- 142
relaxed, 497
running times of operations on, 456 fig.
and treaps, 296 pr.
2-3-4, 473 pr.
HEAP-DECREASE-KEY, 141 ex.
HEAP-DELETE, 142 ex.
HEAP-EXTRACT-MAX, 139
HEAP-EXTRACT-MIN, 141 ex.
HEAP-INCREASE-KEY, 140
HEAP-MAXIMUM, 139
HEAP-MINIMUM, 141 ex.
heap property, 128
maintenance of, 130- 132
vs. binary-search-tree property, 256 ex.
heapsort, 127- 144
HEAPSORT, 136
height
of a binomial tree, 457
black, 274
of a B-tree, 439- 440
of a d-ary heap, 143 pr.
of a decision tree, 167
exponential, 265 of a heap, 129, 129 ex.
of a node in a heap, 129, 135 ex.
of a node in a tree, 1088
of a red-black tree, 274
of a tree, 1088
height-balanced tree, 296 pr.
height function, in push-relabel algorithms, 671
hereditary family of subsets, 393
Hermitian matrix, 759 ex.
high endpoint of an interval, 311
HIRE-ASSISTANT, 92
hiring problem, 91- 92
on-line, 114- 117
probabilistic analysis of, 97- 98
hit, spurious, 912
HOARE-PARTITION, 160 pr.
HOPCROFT-KARP, 696 pr.
Hopcroft-Karp bipartite matching algorithm, 696 pr.
horizontal ray, 940 ex.
Horner's rule, 39 pr., 824
in the Rabin-Karp algorithm, 911
HUFFMAN, 388
Huffman code, 385- 393
hull, convex, 947- 957, 964 pr.
hyperedge, 1083
hypergraph, 1083
and bipartite graphs, 1084 ex.

| < Day Day Up > |