优先队列(priority queue)和堆(heap)

from queue import Queue   # 队列，FIFO
from queue import PriorityQueue  #优先级队列，优先级高的先输出
###############队列（Queue）的使用，/python中也可是用列表（list）来实现队列###############
q = Queue(maxsize) 	#构建一个队列对象，maxsize初始化默认为零，此时队列无穷大
q.empty()		#判断队列是否为空(取数据之前要判断一下)
q.full()		#判断队列是否满了
q.put()			#向队列存放数据
q.get()			#从队列取数据
q.qsize()		#获取队列大小，可用于判断是否满/空
###用法示例：
>>> q = Queue(3)
>>> for i in range(3):
>>>	q.put(i)
>>> q.full()
True
>>> while not q.empty():
>>> 	print(q.get())
0
1
2
###############优先队列（PriorityQueue）的使用###############
"""
队列的变体，按优先级顺序（最低优先）检索打开的条目。
条目通常是以下格式的元组：
插入格式：q.put((priority number, data))
特点：priority number 越小，优先级越高
其他的操作和队列相同
"""
>>> q = PriorityQueue()
>>> q.put((2, "Lisa"))
>>> q.put((1, "Lucy"))
>>> q.put((0, "Tom"))
>>> i = 0
>>> while i < q.qsize()：
>>> 	print(q.get())
(0，"Tom")
(1，"Lucy")
(2，"Lisa")
#可见并没有按照输入的顺序输出的，而是按照优先级顺序输出的
#优先独队列的实质是

class Heap:
	def __init__(self, _list):
		self._list = _list
		self.k = len(_list)
		
	def _bigHeapAdjuest(self, j):
		temp = self._list[j] #存放当前双亲节点的值,j代表当前节点的位置
		i = 2*j  			 #j的左孩子
		while i <= self.k:
			if i < self.k and self._list[i] < self._list[i+1]:  #i==n时由于只有一个子节点，所以没有比较的必要
				i += 1
			#与双亲比较，如果双亲大则跳过
			#如果双亲小，就把大的给双亲
			if temp >= self._list[i]:
				break                 			#没有必要修整
			self._list[j] = self._list[i]       #元素交换
			j = i                               #j记录着temp应该去的位置,由于这个位置的节点发生了变动，所以需要再次调整
			i *= 2             					#接着找该节点的左孩子
		self._list[j] = temp	
	
    def _smallheapAdjuest(self, j):
        temp = self._list[i] #父节点
        i = 2*j  #左孩子
        while i <= self.k:
            if i < self.k and self._list[i] > self._list[i+1]:    #找最小的那个孩子
                i += 1
            #构建小顶堆，小于父节点的都要上浮
            if self._list[i] >= temp:
                break
            self._list[j] = self._list[i]  #子节点交给父节点
            j= i    #记录父节点应该去的索引位置
            i *= 2
        self._list[j] = temp
	
	def heapSort(self):
		self._list.insert(0, -1) 
		s = self.length // 2  
		#构建大顶堆
		for j in range(s, 0, -1):
			self._bigHeapAdjuest(j) 
		#构建小顶堆
			for j in range(s, 0, -1):
			self._SmallheapAdjuest(j)