アルゴリズム導論第6章2優先キュー(python)

優先キュー:
物理構造:シーケンステーブル(典型的には配列){python list}
論理構造ろんりこうぞう:完全二叉木に似ている
使用する特徴は、ダイナミックなソートです.ソートされた要素が増加します.減少#と高速ソートを比較すると、高速で並べ替えられた要素が再配置されます(挿入かもしれません).
プラグアンドプレイ
毎回最大(最大(優先キュー/スタック)または最小
重要なポイント:
A.length:要素個数#python私はlen(A)-1#で1を捨てます
    A.heap_size:スタック内の要素の個数がA.lengthに等しいとは限らない{これは理解しにくいが、スタックソートの最後のステップを見ることができる}
 

'''
      

'''
def PARENT(i):
    return i//2

def LEFT(i):
    return i*2

def RIGHT(i):
    return i*2 + 1


class Mylist(list):
    def __init__(self):
        self.heap_size = 0
        super().__init__()


def MAX_HEAPIFY(A,i):
    l = LEFT(i)
    r = RIGHT(i)

    #       
    
    #i        i
    #A.heap_size       list          （Mylist）
    #    A[0]   heap_size ??
    #        
    if l <= A.heap_size and A[l] > A[i]:
        largest = l
    else:
        largest = i
    #     
    if r <= A.heap_size and A[r] > A[largest]:
        largest = r
    if largest != i: #  A[i]           
        A[i],A[largest] = A[largest],A[i] #  
        MAX_HEAPIFY(A,largest) #   largest

def BUILD_MAX_HEAP(A):
    A.heap_size = len(A)-1
    #print(len(A))
    for i in range(A.heap_size//2,0,-1): # n//2   1
        #print(i)
        MAX_HEAPIFY(A,i)


def HEAP_MAXMUM(A):
    return A[1] #        

def HEAP_EXTRACT_MAX(A): #            HEAPSORT(A)    
    if A.heap_size < 1:
        raise OverflowError("heap underflow")
    max = A[1]
    A[1] = A[A.heap_size]
    A.heap_size -= 1
    MAX_HEAPIFY(A,1)#  
    return max

def HEAP_INCREASE_KEY(A,i,key):#       
    if key < A[i]:
        print("new key is smaller than current key")
        return
    A[i] = key
    while i > 1 and A[PARENT(i)] < A[i]: #  
        A[i],A[PARENT(i)] = A[PARENT(i)],A[i]
        i = PARENT(i)

def MAX_HEAP_INSERT(A,key):#  
    A.heap_size += 1
    A.append(-10000)
    #A[A.heap_size] = -10000#- -!
    HEAP_INCREASE_KEY(A,A.heap_size,key)

    
    
    
    

if __name__ == '__main__':
    A = Mylist()
    for i in[-1,4,1,3,2,16,9,10,14,8,7]: #A = [,...] A   list
        A.append(i)
    BUILD_MAX_HEAP(A)
    print("    :",A)
    MAX_HEAP_INSERT(A,20)
    MAX_HEAP_INSERT(A,5)
    print("     :",A)
    print("      ： ",end='')
    print(HEAP_EXTRACT_MAX(A))
    print("    ",A)
    print("      ： ",end='')
    print(HEAP_EXTRACT_MAX(A))
    print("    ",A)
    
    

'''
============ RESTART: F:/python/algorithms/6_5_priority_queue.py ============
    : [-1, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
     : [-1, 20, 16, 10, 8, 14, 9, 3, 2, 4, 1, 7, 5]
      ： 20
     [-1, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1, 5, 5] #          A.heap_size  
      ： 16
     [-1, 14, 8, 10, 5, 7, 9, 3, 2, 4, 1, 5, 5]

  win7 + python3.5.1
'''