Python最大優先キューを実現

説明:多重性を向上させるために、2つのクラス、Heapクラス、PriorityQクラスが設計され、PriorityQクラスはHeapクラスを継承し、最大スタックベースの最大優先キューを実現します.

#! /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

試験結果:BigHeap 1:[100,98,23,89,34,−5,6,11,0,2,4]Maximun:100 ExtractMax:100 BigHeap 2:[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,30,11,34,−5,6,6,4,0,2][10,98,30,11,89,−5,6,4,4,4,2][100,98,30,11,89,−5