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")
#可见并没有按照输入的顺序输出的，而是按照优先级顺序输出的
#优先独队列的实质是

堆（heap）

看完上面的示例我们也许会有疑惑，优先队列是如何来实现的了？
----------优先队列的实质是每次插入时按照一定的规则插入，删除时直接找到最小的那个元素弹出即可。插入和弹出最坏情况下的时间复杂度都是O(LogN)

下面我们就来介绍实现优先队列的一种数据结构——堆(heap)。

简介

堆的实质是一个完全二叉树(除最底层外，其余层都是满二叉树，且最底层的节点从左往右顺序排列)。 堆主要分为大顶堆和小顶堆两种
1.大顶堆：每个分支的根节点都大于等于其子节点。（k_i >= k_2i）and (k_i >= k_2i+1)
2.小顶堆：每个分支的根节点都小于等于其子节点。（k_i <= k_2i）and (k_i <= k_2i+1)
所以堆中的第i个元素的父亲是floor(i/2)（向下取整）, 第i个元素的左右孩子分别是2i和2i+1

堆的根节点要从1开始计算，不能从0开始计算。(假如从零开始i=2时其父亲节点为floor(2/2)=1, 显然是错误的)

初始化构建堆

将一个有k个元素的数组构成一个大顶堆或者小顶堆。时间复杂度O(n)$
核心思路：从下往上，从右往左，且每次都从第floor(k/2)个元素开始进行调整依次递减直到根节点

1.从floor(k/2)个元素开始进行调整，调整完毕，则i--；
	#调整节点，每次只调整该根节点以下的子树
	while i <= k
		1.1 找出左右孩子中最大的那个
		1.2 该节点和较大的那个子节点比较，
	    	    如果父节点较大，break
	    	    如果子节点较大，记录子节点的索引，把子节点的值给父节点
		1.3 将上面较大的那个字节点作为新的父节点开始一轮循环
	循环结束后，将父节点的值放到他应该去的子节点的位置上

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)