用Python亲手搭建一个优先级队列:纯属练手之作
最编程
2024-07-19 21:26:23
...
最近做实验的时候经常用到优先队列,之前都是用java实现的,今天闲的没事用python写了一个,全当练手~
PS:这是个小顶堆
# Implemented by LiangTE
# 2013.4.12
# Just for Practicing Python
class PriorityQueue:
__pq = [None]
__size = -1
__N = 0
def __init__(self, size):
self.__size = size+1
def insert(self, k):
if len(self.__pq) < self.__size:
self.__pq.append(k)
self.__N += 1
self.__swim(self.__N)
else:
if k > self.__peek():
self.__pq[1] = k
self.__sink(1)
def __peek(self):
return self.__pq[1]
def __sink(self, m):
i = -1
while m*2 <= self.__size:
if self.__pq[m*2] > self.__pq[m*2+1]:
i = m*2 + 1
else:
i = m*2
if self.__pq[m] > self.__pq[i]:
tmp = self.__pq[m]
self.__pq[m] = self.__pq[i]
self.__pq[i] = tmp
m = i
else:
break
def __swim(self, n):
while n > 1:
if self.__pq[n/2] > self.__pq[n]:
tmp = self.__pq[n/2]
self.__pq[n/2] = self.__pq[n]
self.__pq[n] = tmp
n = n/2
def printQuene(self):
print self.__pq[1:]
上一篇: 在C#中玩转优先级队列(简明讲解)