本文實例為大家分享了python實現(xiàn)最大優(yōu)先隊列的具體代碼，供大家參考，具體內容如下

說明：為了增強可復用性，設計了兩個類，Heap類和PriorityQ類，其中PriorityQ類繼承Heap類，從而達到基于最大堆實現(xiàn)最大優(yōu)先隊列。

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

#維護堆的性質：遵循最大堆

def MaxHeapify(self, a, i, heap_size):

l=self.Left(i)

r=self.Right(i)

largest = i

if la[largest]:#下標從0~heap_size-1

largest=l

if ra[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é)點開始調整

#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]構造為堆(堆頂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:為避免交換后新的堆頂違反堆的性質，因此將新的無序區(qū)調整為新

的堆'''

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]處的關鍵字增加到key

def HeapIncreaseKey(self, a, i, key):

if key

print "new key is smaller than current one"

else:

a[i]=key

'''當前元素不斷與其父節(jié)點進行比較，如果當前元素關鍵字較大，則與其

父節(jié)點進行交換。不斷重復此過程'''

while i>0 and a[self.Parent(i)]

總結

以上是生活随笔為你收集整理的python优先队列_python实现最大优先队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。