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

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

 SORTING NETWORKS (614 - 632) 18 pages >>

 MATRIX OPERATIONS (632 - 673) 41 pages >>

 Show All