McGraw Hill Introduction To Algorithms (2nd Ed) >>
HEAPSORT (112 - 127) 15 pages
6 1 1,2,3,4,5,6,7
6 2 1,2,3,4,5
6 3 1,2,3
6 4 1,2,3,4 >>
Running time is O(n lg n).
HEAP is a binary tree.
PARENT(i) = i/2
RIGHT (i) = 2i + 1
LEFT (i) = 2i
Max-Heap & Min-Heap types
Height = Q(lg n) = longest downward path to leaf
HeapSize = Number Of Nodes in the Tree
MAX-HEAPIFY(A, i)
1 l <-- LEFT(i)
2 r <-- RIGHT(i)
3 if l <= heap-size[A] and A[l] > A[i]
4 then largest <-- l
5 else largest <-- i
6 if r <= heap-size[A] and A[r] > A[largest]
7 then largest <-- r
8 if largest != i
9 then exchange A[i] - A[largest]
10 MAX-HEAPIFY(A, largest)
BUILD-MAX-HEAP(A)
1 heap-size[A] <-- length[A]
2 for i <-- |length[A]/2| downto 1
3 do MAX-HEAPIFY(A, i)
Building a Max-Heap is Linear Time = O(n)
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i <-- length[A] downto 2
3 do exchange A[1] - A[i]
4 heap-size[A] <-- heap-size[A] - 1
5 MAX-HEAPIFY(A, 1)
HEAP-MAXIMUM(A)
1 return A[1]
HEAP-EXTRACT-MAX(A)
1 if heap-size[A] < 1
2 then error "heap underflow"
3 max <-- A[1]
4 A[1] <-- A[heap-size[A]]
5 heap-size[A] <-- heap-size[A] - 1
6 MAX-HEAPIFY(A, 1)
7 return max
HEAP-INCREASE-KEY(A, i, key)
1 if key < A[i]
2 then error "new key is smaller than current key"
3 A[i] <-- key
4 while i > 1 and A[PARENT(i)] < A[i]
5 do exchange A[i] - A[PARENT(i)]
6 i <-- PARENT(i)
MAX-HEAP-INSERT(A, key)
1 heap-size[A] <-- heap-size[A] + 1
2 A[heap-size[A]] <-- -oo
3 HEAP-INCREASE-KEY(A, heap-size[A], key)
|
SORTING IN LINEAR TIME (145 - 160) 15 pages
8 1 1,2,3,4*
8 3 1,2,3,4,5*
8 4 1,2
8 Pro 2,4,6 >>
COUNTING-SORT(A, B, k)
1 for i <-- 0 to k
2 do C[i] <-- 0
3 for j <-- 1 to length[A]
4 do C[A[j]]<-- C[A[j]] + 1
5 > C[i] now contains the number of elements equal to i.
6 for i <-- 1 to k
7 do C[i] <-- C[i] + C[i - 1]
8 > C[i] now contains the number of elements less than or equal to i.
9 for j <-- length[A] downto 1
10 do B[C[A[j]]] <-- A[j]
11 C[A[j]] <-- C[A[j]] - 1
Counting Sort is Stable... (The Equal Values are in given order in the Result)
RADIX-SORT(A, d)
1 for i <-- 1 to d
2 do use a stable sort to sort array A on digit i
BUCKET-SORT(A)
1 n <-- length[A]
2 for i <-- 1 to n
3 do insert A[i] into list B[|n A[i]|]
4 for i <-- 0 to n - 1
5 do sort list B[i] with insertion sort
6 concatenate the lists B[0], B[1], . . ., B[n - 1] together in order
|
HASH TABLES (192 - 219) 27 pages
11 1 1,2,3
11 2 1,2,3,4*
11 3 1,2,3,4
11 4 1,2,3,4 >>
HASH TABLES
insert, search, delete operations
Dİrect Adrress Tables
Aim is run in O(1) time.
Collision resolution by chaining
In open addressing, all elements are stored in the hash table itself.
Choose a hash table size, to be prime and not to near a power of 2
h'(k) = ((ak + b)%p)%m
Linear Probing : h(k, i) = (h'(k) + i) mod m
Quadratic Probing : h(k, i) = (h'(k) + s.i + t.i^2) mod m
Double Probing : h(k, i) = (h1(k) + i.h2(k)) mod m
Perfect Hashing : We use chaining with another hashing
|
BINARY SEARCH TREES (220 - 238) 18 pages
12 1 1,2,3,4,5
12 2 1,2,3,4,5,6,7,8,9
12 3 1,2,3,4,6 >>
BINARY SEARCH TREES
Search, Minimum, Maximum, Predecessor, Successor, Insert & Delete Operations
INORDER-TREE-WALK(x) // LEFT-TOP-RIGHT
1 if x != NIL
2 then INORDER-TREE-WALK(left[x])
3 print key[x]
4 INORDER-TREE-WALK(right[x])
PREORDER-TREE-WALK(x) // TOP-LEFT-RIGHT
POSTORDER-TREE-WALK(x) // LEFT-RIGHT-TOP
TREE-SEARCH (x, k)
1 if x= NIL or k = key[x]
2 then return x
3 if k < key[x]
4 then return TREE-SEARCH(left[x], k)
5 else return TREE-SEARCH(right[x], k)
SUCCESSOR : minimum key in the right subtree
ITERATIVE-TREE-SEARCH(x, k)
1 while x != NIL and k != key[x]
2 do if k < key[x]
3 then x <-- left[x]
4 else x <-- right[x]
5 return x
TREE-MINIMUM (x)
1 while left[x] != NIL
2 do x <-- left[x]
3 return x
TREE-SUCCESSOR(x)
1 if right[x] != NIL
2 then return TREE-MINIMUM (right[x])
3 y <-- p[x]
4 while y!= NIL and x = right[y]
5 do x <-- y
6 y <-- p[y]
7 return y
TREE-INSERT(T, z)
1 y <-- NIL
2 x <-- root[T]
3 while x != NIL
4 do y <-- x
5 if key[z] < key[x]
6 then x <-- left[x]
7 else x <-- right[x]
8 p[z] <-- y
9 if y = NIL
10 then root[T] <-- z // Tree T was empty
11 else if key[z] < key[y]
12 then left[y] <-- z
13 else right[y] <-- z
TREE-DELETE(T, z)
1 if left[z] = NIL or right[z] = NIL
2 then y <-- z
3 else y <-- TREE-SUCCESSOR(z)
4 if left[y] != NIL
5 then x <-- left[y]
6 else x <-- right[y]
7 if x != NIL
8 then p[x] <-- p[y]
9 if p[y] = NIL
10 then root[T] <-- x
11 else if y = left[p[y]]
12 then left[p[y]] <-- x
13 else right[p[y]] <-- x
14 if y != z
15 then key[z] <-- key[y]
16 copy y's satellite data into z
17 return y
|
RED-BLACK TREES (238 - 261) 23 pages
13 1 1,2,6
13 2 1,2,3
13 3 1,2, 3, 6
13 4 1, 2, 3, 4, 6, 7 >>
RED-BLACK TREES
1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.
A red-black tree with n internal nodes has height at most 2 lg(n + 1).
LEFT-ROTATE(T, x)
1 y <-- right[x] > Set y.
2 right[x] <-- left[y] > Turn y's left subtree into x's right subtree.
3 p[left[y]] <-- x
4 p[y] <-- p[x] > Link x's parent to y.
5 if p[x] = nil[T]
6 then root[T] <-- y
7 else if x = left[p[x]]
8 then left[p[x]] <-- y
9 else right[p[x]] <-- y
10 left[y] <-- x > Put x on y's left.
11 p[x] <-- y
RB-INSERT(T, z)
1 y <-- nil[T]
2 x <-- root[T]
3 while x != nil[T]
4 do y <-- x
5 if key[z] < key[x]
6 then x <-- left[x]
7 else x <-- right[x]
8 p[z] <-- y
9 if y = nil[T]
10 then root[T] <-- z
11 else if key[z] < key[y]
12 then left[y] <-- z
13 else right[y] <-- z
14 left[z] <-- nil[T]
15 right[z] <-- nil[T]
16 color[z] <-- RED
17 RB-INSERT-FIXUP(T, z)
RB-INSERT-FIXUP(T, z)
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y <-- right[p[p[z]]]
4 if color[y] = RED
5 then color[p[z]] <-- BLACK > Case 1
6 color[y] <-- BLACK > Case 1
7 color[p[p[z]]] <-- RED > Case 1
8 z <-- p[p[z]] > Case 1
9 else if z = right[p[z]]
10 then z <-- p[z] > Case 2
11 LEFT-ROTATE(T, z) > Case 2
12 color[p[z]] <-- BLACK > Case 3
13 color[p[p[z]]] <-- RED > Case 3
14 RIGHT-ROTATE(T, p[p[z]]) > Case 3
15 else (same as then clause with "right" and "left" exchanged)
16 color[root[T]] <-- BLACK
RB-DELETE(T, z)
1 if left[z] = nil[T] or right[z] = nil[T]
2 then y <-- z
3 else y <-- TREE-SUCCESSOR(z)
4 if left[y] != nil[T]
5 then x <-- left[y]
6 else x <-- right[y]
7 p[x] <-- p[y]
8 if p[y] = nil[T]
9 then root[T] <-- x
10 else if y = left[p[y]]
11 then left[p[y]] <-- x
12 else right[p[y]] <-- x
13 if y 3 != z
14 then key[z] <-- key[y]
15 copy y's satellite data into z
16 if color[y] = BLACK
17 then RB-DELETE-FIXUP(T, x)
18 return y
RB-DELETE-FIXUP(T, x)
1 while x != root[T] and color[x] = BLACK
2 do if x = left[p[x]]
3 then w <-- right[p[x]]
4 if color[w] = RED
5 then color[w] <-- BLACK > Case 1
6 color[p[x]] <-- RED > Case 1
7 LEFT-ROTATE(T, p[x]) > Case 1
8 w <-- right[p[x]] > Case 1
9 if color[left[w]] = BLACK and color[right[w]] = BLACK
10 then color[w] <-- RED > Case 2
11 x p[x] > Case 2
12 else if color[right[w]] = BLACK
13 then color[left[w]] <-- BLACK > Case 3
14 color[w] <-- RED > Case 3
15 RIGHT-ROTATE(T, w) > Case 3
16 w <-- right[p[x]] > Case 3
17 color[w] <-- color[p[x]] > Case 4
18 color[p[x]] <-- BLACK > Case 4
19 color[right[w]] <-- BLACK > Case 4
20 LEFT-ROTATE(T, p[x]) > Case 4
21 x <-- root[T] > Case 4
22 else (same as then clause with "right" and "left" exchanged)
23 color[x] <-- BLACK
|
B-TREES (371 - 388) 17 pages
18 1 1, 2, 3, 4, 5
18 2 1, 3, 5, 6 >>
B-TREES
> n keys, n+1 children
> a fixed integer t >= 2 called the minimum degree
> Every node other than the root must have at least t - 1 keys, t children.
> Every node can contain at most 2t - 1 keys, 2t children.
> at depth h there are at least 2t^(h-1) nodes
B-Tree-Search(x, k)
i <- 1
while i <= n[x] and k > keyi[x]
do i <- i + 1
if i <= n[x] and k = keyi[x]
then return (x, i)
if leaf[x]
then return NIL
else Disk-Read(ci[x])
return B-Tree-Search(ci[x], k)
B-Tree-Create(T)
x <- Allocate-Node()
leaf[x] <- TRUE
n[x] <- 0
Disk-Write(x)
root[T] <- x
B-Tree-Split-Child(x, i, y)
z <- Allocate-Node()
leaf[z] <- leaf[y]
n[z] <- t - 1
for j <- 1 to t - 1
do keyj[z] <- keyj+t[y]
if not leaf[y]
then for j <- 1 to t
do cj[z] <- cj+t[y]
n[y] <- t - 1
for j <- n[x] + 1 downto i + 1
do cj+1[x] <- cj[x]
ci+1 <- z
for j <- n[x] downto i
do keyj+1[x] <- keyj[x]
keyi[x] <- keyt[y]
n[x] <- n[x] + 1
Disk-Write(y)
Disk-Write(z)
Disk-Write(x)
B-Tree-Insert(T, k)
r <- root[T]
if n[r] = 2t - 1
then s <- Allocate-Node()
root[T] <- s
leaf[s] <- FALSE
n[s] <- 0
c1 <- r
B-Tree-Split-Child(s, 1, r)
B-Tree-Insert-Nonfull(s, k)
else B-Tree-Insert-Nonfull(r, k)
B-Tree-Insert-Nonfull(x, k)
i <- n[x]
if leaf[x]
then while i >= 1 and k < keyi[x]
do keyi+1[x] <- keyi[x]
i <- i - 1
keyi+1[x] <- k
n[x] <- n[x] + 1
Disk-Write(x)
else while i >= and k < keyi[x]
do i <- i - 1
i <- i + 1
Disk-Read(ci[x])
if n[ci[x]] = 2t - 1
then B-Tree-Split-Child(x, i, ci[x])
if k > keyi[x]
then i <- i + 1
B-Tree-Insert-Nonfull(ci[x], k)
|
BINOMIAL HEAPS (388 - 405) 17 pages
19 1 1, 2
19 2 1, 2, 3, 5, 7 >>
BINOMIAL HEAPS
Make-Heap, Insert, Minimum, Extract-Min, Uninon, Decrease-Key & Delete Operations
the UNION operation takes only O(lg n) time to merge two binomial heaps
For the binomial tree Bk,
1. there are 2^k nodes,
2. the height of the tree is k
B0 --> B1 --> B2 --> ... (siblings)
BINOMIAL-HEAP-MINIMUM(H)
1 y <-- NIL
2 x <-- head[H]
3 min <-- oo
4 while x != NIL
5 do if key[x] < min
6 then min <-- key[x]
7 y <-- x
8 x <-- sibling[x]
9 return y
BINOMIAL-LINK(y, z)
1 p[y] <-- z
2 sibling[y] <-- child[z]
3 child[z] <-- y
4 degree[z] <-- degree[z] + 1
BINOMIAL-HEAP-UNION(H1, H2)
1 H <-- MAKE-BINOMIAL-HEAP()
2 head[H] <-- BINOMIAL-HEAP-MERGE(H1, H2)
3 free the objects H1 and H2 but not the lists they point to
4 if head[H] = NIL
5 then return H
6 prev-x <-- NIL
7 x <-- head[H]
8 next-x <-- sibling[x]
9 while next-x != NIL
10 do if (degree[x] != degree[next-x]) or (sibling[next-x] != NIL and degree[sibling[next-x]] = degree[x])
11 then prev-x <-- x > Cases 1 and2
12 x <-- next-x > Cases 1 and 2
13 else if key[x] <= key[next-x]
14 then sibling[x] <-- sibling[next-x] > Case 3
15 BINOMIAL-LINK(next-x, x) > Case 3
16 else if prev-x = NIL > Case 4
17 then head[H] <-- next-x > Case 4
18 else sibling[prev-x] <-- next-x > Case 4
19 BINOMIAL-LINK(x, next-x) > Case 4
20 x <-- next-x > Case 4
21 next-x <-- sibling[x]
22 return H
BINOMIAL-HEAP-INSERT(H, x)
1 H' <-- MAKE-BINOMIAL-HEAP()
2 p[x] <-- NIL
3 child[x] <-- NIL
4 sibling[x] <-- NIL
5 degree[x] <-- 0
6 head[H'] <-- x
7 H <-- BINOMIAL-HEAP-UNION(H, H')
BINOMIAL-HEAP-EXTRACT-MIN(H)
1 find the root x with the minimum key in the root list of H, and remove x from the root list of H
2 H' <-- MAKE-BINOMIAL-HEAP()
3 reverse the order of the linked list of x's children, and set head[H'] to point to the head of the resulting list
4 H <-- BINOMIAL-HEAP-UNION(H, H')
5 return x
|
SORTING NETWORKS (614 - 632) 18 pages >>
SORTING NETWORKS
Comparator : takes min to top, max to bottom
Half-Cleaner : bitonic to (bitonic and clean) [i to (n/2)+i]
Bitonic-Sorter : ...-4n-2.2n-4.n-... half cleaners
Merging Network : Merger8 + 2.Bitonic4 + 4.Bitonic2 (HC)
Sorting Network : 4.Merger2 + 2.Merger4 + Merger8
|
MATRIX OPERATIONS (632 - 673) 41 pages >>
MATRIX OPERATIONS
nxm matrix has n rows and m coloumns
vector is a one-dimensional array of numbers
transpose obtained by exchanging the rows and columns
A matrix without an inverse is called noninvertible, or singular
LU decomposition (lower-upper) [Ax = b, LUx = b, Ly = b]
LU-DECOMPOSITION(A)
1 n <-- rows[A]
2 for k <-- 1 to n
3 do ukk <-- akk
4 for i <-- k + 1 to n
5 do lik <-- aik/ukk > lik holds vi
6 uki <-- aki > uki holds
7 for i <-- k + 1 to n
8 do for j <-- k + 1 to n
9 do aij <-- aij - lik.ukj
10 return L and U
|
Show All