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

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


#最大優先隊列的實現
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 #該處不對，并沒有真正實現數組長度減一
   del a[heap_size-1]#!!!!!!
   self.MaxHeapify(a, 0, len(a))
   return max
 #將a[i]處的關鍵字增加到key
 def HeapIncreaseKey(self, a, i, key):
  if key<a[i]:
   print "new key is smaller than current one"
  else:
   a[i]=key
   '''當前元素不斷與其父節點進行比較，如果當前元素關鍵字較大，則與其
    父節點進行交換。不斷重復此過程'''
   while i>0 and a[self.Parent(i)]<a[i]:
    a[i], a[self.Parent(i)] = a[self.Parent(i)], a[i]
    i=self.Parent(i) 

 #增加元素
 def MaxHeapInsert(self, a, key):
  #heap_size=len(a)
  #heap_size += 1
  #a[heap_size-1]=-65535
  a.append(-65535)#在a的末尾增加一個關鍵字為負無窮的葉節點擴展最大堆
  heap_size=len(a)
  self.HeapIncreaseKey(a, heap_size-1, key)


if __name__ == '__main__':
 H = Heap()
 P = PriorityQ()
 x = [0, 2, 6, 98, 34, -5, 23, 11, 89, 100, 4]
 #x1= [3,9,8,4,5,2,10,18]
 #H.HeapSort(x)
 #H.HeapSort(x1)
 #print x
 #print x1
 H.BuildMaxHeap(x)#首先建立大頂堆
 print '%s %r' % ('BigHeap1:', x) # %r是萬能輸出格式
 print '%s %d' % ('Maximun:', P.HeapMaximum(x))
 print '%s %d' % ('ExtractMax:', P.HeapExtractMax(x))
 print '%s %r' % ('BigHeap2:', x)
 #P.MaxHeapInsert(x, 100)
 #print x
 P.HeapIncreaseKey(x, 2, 20)
 print x
 P.HeapIncreaseKey(x, 2, 30)
 print x
 P.MaxHeapInsert(x, 100)
 print x

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]