 |  Introduction to Algorithms, 2/e Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
Heapsort
Glossary
| record | each number to be sorted is usually part of a collection of data called a record
(See page 123)
| | | | | key | Each record contains a key, which is the value to be sorted, and the remainder of the record consists of satellite data, which are usually carried around with the key.
(See page 123)
| | | | | (binary) heap data structure | an array object that can be viewed as a nearly complete binary tree
(See page 125)
| | | | | max-heap property | In a max-heap, the max-heap property is that for every node i other than the root, A[PARENT(i)] ≥ A[i], that is, the value of a node is at most the value of its parent.
(See page 128)
| | | | | min-heap property | A min-heap is organized in the opposite way from the max-heap; the min-heap property is that for every node i other than the root, A[PARENT(i)] ≤ A[i].
(See page 129)
| | | | | height | Viewing a heap as a tree, we define the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf, and we define the height of the heap to be the height of its root.
(See page 129)
| | | | | priority queue | a data structure for maintaining a set S of elements, each with an associated value called a key.
(See page 138)
| | | | | max-priority queue | supports the following operations. INSERT(S, x) inserts the element x into the set S. This operation could be written as S ← S ∪ {x}. MAXIMUM(S) returns the element of S with the largest key. EXTRACT-MAX(S) removes and returns the element of S with the largest key. INCREASE-KEY(S, x, k) increases the value of element x's key to the new value k, which is assumed to be at least as large as x's current key value. One application of max-priority queues is to schedule jobs on a shared computer.
(See page 138)
| | | | | min-priority queue | supports the operations INSERT, MINIMUM, EXTRACT-MIN, and DECREASE-KEY. The min-priority queue can be used in an event-driven simulator.
(See page 138)
| | | | | monotone | the values returned by successive EXTRACT-MIN operations are monotonically increasing over time.
(See page 144)
|
|
2002 McGraw-Hill Higher Education