Heapsort

+ Complete binary tree
    - filled on all levels except the lowest, which is filled from left up to a point
    - array format:
   index:   0 1 2 3 4 5 6 7 8 9
           +-+-+-+-+-+-+-+-+-+-+
   value:  |9|8|7|6|5|4|3|2|1|0|
           +-+-+-+-+-+-+-+-+-+-+
    - parent index of a node index i:       i / 2
    - left child index of a node index i:   2i
    - right child index of a node index i: 2i + 1

+ Max heap
    - A[parent(i)] >= A[i]
    - the max element is stored at the root



+ Heapsort procedures
  heap_sort(A):                       // O(nlgn) time
      build_max_heap(A)               // build a max heap
      heap_size = len(A)
      for i in range(len(A), -1, 1):  // from last to second
          A[0], A[i] = A[i], A[0]     // put current max at heap end
          heap_size -= 1
          max_heapify(A, 0, heap_size)  // flow A[0] down

  # build a max heap from an unsorted array
  build_max_heap(A):                  // O(n) time. Yes, linear.
      for i in range(len(A) / 2, -1, 0):
          max_heapify(A, i, len(A))

  # build a max heap at i
  # assumption: left(i) and right(i) are already max heaps
  max_heapify(A, i, heap_size):       // O(lgn)
      left = 2 * i
      right = 2 * i + 1
      largest = i
      if left < heap_size and A[left] > A[i]:
          largest = left
      if right < heap_size and A[right] > A[largest]:
          largest = right
      if largest != i:
          A[largest], A[i] = A[i], A[largest]
          max_heapify(A, largest, heap_size)

+ Priority queue maintaining a set A of elements
  # read the max element in current queue
  heap_max(A):
      return A[0]

  # pop the max element in current queue
  heap_extract_max(A):
      if heap_size < 1:
          print 'heap underflow'
          return None
      max = A[0]
      A[0] = A[heap_size]
      heap_size -= 1
      max_heapify(A, 0, heap_size)
      return max

  # increase a value of an element
  heap_increase_key(A, i, key):
      if key < i:
          print 'invalid value'
          return
      A[i] = key
      while i > 0 and A[i] > A[parent(i)]:
          A[i], A[parent(i)] = A[parent(i)], A[i]
          i = parent(i)    // flow the key up

  # insert a new element of value key into the queue
  heap_insert(A, key):
      heap_size += 1
      A[heap_size] = -sys.maxint - 1
      heap_increase_key(A, heap_size, key)

  Note: all these operations require O(lgn) time.