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)