您好,登錄后才能下訂單哦!
本文實(shí)例為大家分享了python實(shí)現(xiàn)最大優(yōu)先隊(duì)列的具體代碼,供大家參考,具體內(nèi)容如下
說明:為了增強(qiáng)可復(fù)用性,設(shè)計(jì)了兩個(gè)類,Heap類和PriorityQ類,其中PriorityQ類繼承Heap類,從而達(dá)到基于最大堆實(shí)現(xiàn)最大優(yōu)先隊(duì)列。
#! /usr/bin/env python #coding=utf-8 class Heap(object): #求給定下標(biāo)i的父節(jié)點(diǎn)下標(biāo) def Parent(self, i): if i%2==0: return i/2 - 1 else: return i/2 #求給定下標(biāo)i的左孩子下標(biāo) def Left(self, i): return 2*i+1 #求給定下標(biāo)i的右孩子下標(biāo) def Right(self, i): return 2*i+2 #維護(hù)堆的性質(zhì):遵循最大堆 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]:#下標(biāo)從0~heap_size-1 largest=l if r<heap_size and a[r]>a[largest]: largest=r if largest!=i:#若當(dāng)前節(jié)點(diǎn)不是最大的,下移 a[i], a[largest] = a[largest], a[i]#交換a[i]和a[largest] self.MaxHeapify(a, largest, heap_size)#追蹤下移的節(jié)點(diǎn) #建堆 def BuildMaxHeap(self, a): heap_size=len(a) for i in range(heap_size/2 - 1, -1, -1):#從最后一個(gè)非葉節(jié)點(diǎn)開始調(diào)整 #a[heap_size/2 - 1]~a[0]都是非葉節(jié)點(diǎn),其他的是葉子節(jié)點(diǎn) 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:將當(dāng)前無序區(qū)的堆頂元素a[0]與該區(qū)間最后一個(gè)記錄交換 得到新的無序區(qū)a[0...n-2]和新的有序區(qū)a[n-1],有序區(qū)的范圍從 后往前不斷擴(kuò)大,直到有n個(gè)''' 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)先隊(duì)列的實(shí)現(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 #該處不對(duì),并沒有真正實(shí)現(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<a[i]: print "new key is smaller than current one" else: a[i]=key '''當(dāng)前元素不斷與其父節(jié)點(diǎn)進(jìn)行比較,如果當(dāng)前元素關(guān)鍵字較大,則與其 父節(jié)點(diǎn)進(jìn)行交換。不斷重復(fù)此過程''' 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的末尾增加一個(gè)關(guān)鍵字為負(fù)無窮的葉節(jié)點(diǎn)擴(kuò)展最大堆 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
測試結(jié)果:
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]
以上就是本文的全部內(nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。