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 >>

 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 >>

 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 >>

 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 >>

 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 >>

 B-TREES (371 - 388) 17 pages
  18    1    1, 2, 3, 4, 5
  18    2    1, 3, 5, 6 >>

 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 >>

 MATRIX OPERATIONS (632 - 673) 41 pages >>

 Show All