#! /usr/bin/env python
#coding=utf-8

class Heap(object):
  #求給定下標i的父節(jié)點下標
  def Parent(self, i):
    if i%2==0:
      return i/2 - 1
    else:
      return i/2
  #求給定下標i的左孩子下標
  def Left(self, i):
    return 2*i+1
  #求給定下標i的右孩子下標
  def Right(self, i):
    return 2*i+2
  #維護堆的性質(zhì)：遵循最大堆
  def MaxHeapify(self, a, i, heap_size):
    l=self.Left(i)
    r=self.Right(i)
    largest = i
    if l
            
              a[largest]:#下標從0~heap_size-1
      largest=l
    if r
              
                a[largest]:
      largest=r
    if largest!=i:#若當前節(jié)點不是最大的，下移
      a[i], a[largest] = a[largest], a[i]#交換a[i]和a[largest]
      self.MaxHeapify(a, largest, heap_size)#追蹤下移的節(jié)點
  #建堆 
  def BuildMaxHeap(self, a):
    heap_size=len(a)
    for i in range(heap_size/2 - 1, -1, -1):#從最后一個非葉節(jié)點開始調(diào)整
      #a[heap_size/2 - 1]~a[0]都是非葉節(jié)點，其他的是葉子節(jié)點
      self.MaxHeapify(a, i, heap_size)
  #堆排序算法  
  def HeapSort(self, a):
    heap_size=len(a)
    '''step1:初始化堆，將a[0...n-1]構(gòu)造為堆（堆頂a[0]為最大元素）'''
    self.BuildMaxHeap(a)
    for i in range(len(a)-1, 0, -1):
      #print a
      '''step2:將當前無序區(qū)的堆頂元素a[0]與該區(qū)間最后一個記錄交換
        得到新的無序區(qū)a[0...n-2]和新的有序區(qū)a[n-1],有序區(qū)的范圍從
        后往前不斷擴大，直到有n個'''
      a[0], a[i] = a[i], a[0]#每次將剩余元素中的最大者放到最后面a[i]處 
      heap_size -= 1
      '''step3:為避免交換后新的堆頂違反堆的性質(zhì)，因此將新的無序區(qū)調(diào)整為新
        的堆'''
      self.MaxHeapify(a, 0, heap_size)


#最大優(yōu)先隊列的實現(xiàn)
class PriorityQ(Heap):
  #返回具有最大鍵字的元素
  def HeapMaximum(self, a):
    return a[0]
  #去掉并返回具有最大鍵字的元素
  def HeapExtractMax(self, a):
    heap_size=len(a)
    #if heap_size<0:
    #  error "heap underflow"
    if heap_size>0:
      max=a[0]
      a[0]=a[heap_size-1]
      #heap_size -= 1 #該處不對，并沒有真正實現(xiàn)數(shù)組長度減一
      del a[heap_size-1]#!!!!!!
      self.MaxHeapify(a, 0, len(a))
      return max
  #將a[i]處的關(guān)鍵字增加到key
  def HeapIncreaseKey(self, a, i, key):
    if key
                
                  0 and a[self.Parent(i)]
                
                
                
              
            
          

            
BigHeap1: [100, 98, 23, 89, 34, -5, 6, 11, 0, 2, 4] 
Maximun: 100 
ExtractMax: 100 
BigHeap2: [98, 89, 23, 11, 34, -5, 6, 4, 0, 2] 
new key is smaller than current one 
[98, 89, 23, 11, 34, -5, 6, 4, 0, 2] 
[98, 89, 30, 11, 34, -5, 6, 4, 0, 2] 
[100, 98, 30, 11, 89, -5, 6, 4, 0, 2, 34]