#encoding:utf-8

class MinHeap():
	def __init__(self):
		self.__list = []

	def push(self,n):
		self.__list.append(n)
		self.swim(len(self.__list)-1)

	def pop(self):
		# if len(self.__: return None

		top = self.__list[0]
		self.__list[0] = self.__list[-1]
		self.__list.pop()
		self.sink(0)
		return top

	def is_empty(self):
		return len(self.__list) == 0

	def get_all(self):
		return self.__list

	def get_index(self,data):
		return self.__list.index(data)

	def swim(self,p):
		while p > 0 and self.__list[p]<self.__list[int((p-1)/2)]:
			parent = int((p-1)/2)
			self.__list[p],self.__list[parent] = self.__list[parent],self.__list[p]
			p = parent

	def sink(self,p):
		while p < len(self.__list):
			left = (p<<1)+1 if (p<<1)+1 < len(self.__list) else None
			right = left + 1 if left is not None and left < len(self.__list) - 1 else None

			left_key = self.__list[left] if left is not None else None
			right_key = self.__list[right] if right is not None else None
			p_key = self.__list[p]

			left_lt_p = left_key < p_key if left_key is not None else False
			right_lt_p = right_key < p_key if right_key is not None else False
			left_lt_right = left_key <= right_key if left_key is not None and right_key is not None else True if right_key is None else False
			right_lt_left = left_key > right_key if left_key is not None and right_key is not None else True if left_key is None else False

			if left_lt_p and left_lt_right:
				self.__list[left],self.__list[p] = self.__list[p],self.__list[left]
				p = left
			elif right_lt_p and not right_lt_left:
				self.__list[right],self.__list[p] = self.__list[p],self.__list[right]
				p = right
			else:
				break
	
def test():		
	src = [7,7,5,9,8,6,3,4,2,1,9,8,3,667,2,5,2,5,2,666]
	h = MinHeap()
	for n in src:
		h.push(n)

	print([h.pop() for i in range(0,len(src))])
	print(h.is_empty())

if __name__ == '__main__':
	test()