python實現(xiàn)最大優(yōu)先隊列-創(chuàng)新互聯(lián)

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

為興山等地區(qū)用戶提供了全套網(wǎng)頁設計制作服務，及興山網(wǎng)站建設行業(yè)解決方案。主營業(yè)務為網(wǎng)站制作、成都做網(wǎng)站、興山網(wǎng)站設計，以傳統(tǒng)方式定制建設網(wǎng)站，并提供域名空間備案等一條龍服務，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！

說明：為了增強可復用性，設計了兩個類，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 key0 and a[self.Parent(i)]            

            新聞名稱：python實現(xiàn)最大優(yōu)先隊列-創(chuàng)新互聯(lián)            

            URL分享：http://m.jiaotiyi.com/article/cogipd.html