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.

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.