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.headin 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
heightof 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.