堆是什么鬼？
在学数据结构的时候，链表、堆栈、树三种数据结构印象最深刻。当时理解有误区，堆栈被当成一种结构，可能因为堆栈有同样的特性——只关心堆顶或栈顶的元素。
但是堆结构和栈结构不同，栈结构不关心除栈顶之外的元素，而整个堆是有结构的。本文介绍一种最小堆，利用完全二叉树结构实现。
应用：多路快排
[引至第七城市])
最小堆
首先介绍另一个概念，优先队列。元素添加到队列之后，按照元素的大小顺序，小的元素先出队列。
朴素思想是采用快速排序，选最小的。那么，出队复杂度O(1)，入队复杂度二分查找O(logn)。但每次插入，都需要移动O(n)的元素。
最小堆实现
- 完全二叉树
- 父节点小于他的子节点
操作方法：添加节点（上旋）
- 添加到树中最后一个节点位置，完全二叉树最后一个节点位置固定。
- 如果小于父亲节点，那么与父亲节点交换位置，直到没有父亲节点（根节点）。
操作方法：获取最小值（下旋）
- 堆顶元素(二叉树的根节点)即是最小值，
- 将二叉树的最后一个节点放到根节点上，如果该节点小于子节点，与子节点交换，直至没有子节点。两个子节点，选择最小的子节点替换。
Python代码
利用列表List实现堆、完全二叉树，可以参考第一张图，形象化理解。
class MiniHeap(object):
def __init__(self):
self.heap = []
self.count = 0
def swap(self,i,j):
tmp = self.heap[i]
self.heap[i] = self.heap[j]
self.heap[j] = tmp
def swapUp(self,index):
while(index>0):
parent = (index-1)//2
if(self.heap[parent] > self.heap[index] ):
self.swap(parent,index)
index = parent
else:
break
def swapDown(self,index):
lchild = index*2+1 # 左孩子的序号
while lchild<self.count :# 左孩子存在
rchild = lchild+1
if(rchild<self.count and self.heap[rchild] < self.heap[lchild] and self.heap[rchild] < self.heap[index] ):
self.swap(index,rchild)
index = rchild
lchild = index*2+1
elif(self.heap[lchild]<self.heap[index]):
self.swap(index,lchild)
index = lchild
lchild = index*2+1
else:
break
def pop(self):
assert(self.count>0)
ret = self.heap[0]
self.count = self.count-1
if(self.count > 0):
self.heap[0] = self.heap[self.count]
self.swapDown(0)
self.heap.pop()
return ret
def top(self):
assert(self.count>0)
return self.heap[0]
def insert(self,item):
self.heap.append(item)
self.count = self.count+1
self.swapUp(self.count-1)
