本文實例為大家分享了python實現最大優先隊列的具體代碼，供大家參考，具體內容如下
說明： 為了增強可復用性，設計了兩個類，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
a[largest]:#下標從0~heap_size-1
largest=l
if 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
0 and a[self.Parent(i)]
測試結果：
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]
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
