今天是算法和数据结构的第21篇，我们来聊一个新的数据结构——堆(heap)。
和链表、二叉树以及数组这些热门的数据结构相比，堆相对比较冷门。如果你对数据结构了解不深的话，可能很少听说。但是我们经常用到它，虽然可能你并不一定能感知到。比如说优先队列，我们就经常使用。我们需要用到这样一个数据结构，能够根据我们存入数据的优先级进行排序，将优先级高的排在前面。在和调度相关的一些系统和算法当中，优先队列是必然会用到的。但是很少有人知道，优先队列说是一个队列，但其实是通过堆实现的。
那么堆究竟是一个怎样的数据结构呢？
堆的定义堆的实质其实是二叉树，并且还不是一般的二叉树，而是比较特别的二叉树。
特别在什么地方呢，在于这棵二叉树除了叶子之外的所有节点都是“满”的。所谓的满，也就是没有空缺的意思。
从上图当中我们可以看到，如果去掉最后一层，那么这棵二叉树就是全满的。最后一层叶子节点也是有要求的，要求叶子节点都靠左对齐。满足这两个条件的二叉树成为完全二叉树（complete binary tree）。这个概念如果记不住也没有关系，我好像也只在堆当中遇到。
堆是完全二叉树，但是显然不是所有的完全二叉树都是堆，堆还有一个特殊的性质，就是大小的传递性。
堆根据大小传递性的不同分为大顶堆和小顶堆，所谓的大顶堆就是堆顶的元素也就是树根的元素是最大的。如果是小顶堆则相反，堆顶元素是最小的。所以这两者基本一样，我们就以大顶堆举例。这个传递性其实很好理解，其实只有一条，就是所有节点的值大于它两个孩子的值。也就是说从树根到树叶每一条路径都是递减的。
我们可以看下这张图：
100有两个孩子节点，19和36，100比19和36都大。19有两个孩子17和3，19比它们都大。这应该是很好理解的，堆巧妙的点在哪里呢，巧妙的点在于我们可以用数组来存储这个结构，而不需要自己建树。用数组存储的方法也很简单，我们给图上的点标上下标，可以得到：
我们找下规律，可以发现对于一个树上的一个节点，假设它在数组当中的下标是i的话。那么它的左孩子的下标是i * 2 1， 它的右孩子下标为i * 2 2，它的父节点是(i - 1) // 2。
有了这个规律之后，我们只要知道某个点的坐标，就可以知道它的父亲和两个孩子的坐标。这也是用数组来存储堆非常巧妙和方便的点。
堆的插入有了这个性质有什么用呢？其实很有用，我们可以利用它非常方便地完成堆的维护。
想象一下，首先，往堆的末尾插入元素并不会破坏完全二叉树这个性质。因为完全二叉树的叶子节点是往左对齐的，我们插入元素必然也是在最左边，所以不管我们插入的元素数值是多大，这都不会影响完全二叉树这个性质。但是显然，我们插入的数值大小会影响堆结构的正确性，比如如果我们插入9，插入的位置就不满足大顶堆的性质了。
这个时候，为了维护堆的性质我们需要调整当中的数据。所以其实堆插入元素的过程就是一个调整顺序的过程，那怎么调整呢，其实很简单，就是将我们插入的元素向上比较，如果它比它的父节点元素更大，那么就将它和父节点进行交换，一直到它小于父节点或者是它称为堆顶为止。
假如说，我们插入的元素不是9，而是105，那么最后得到的结果应该是这样的：
这个就是堆的插入过程，因为我们只有插入的位置可能会导致破坏堆结构，所以我们只需要从插入的位置开始往上维护即可。其余的位置并不会影响，并且对于整个这条链路上可能会被影响的节点而言，它们只可能变大，不可能减小，因此也不会出现交换了之后有新的不满足堆性质的情况产生。
由于这个插入的过程是自下而上的，因此整个过程也被称为是向上更新。
我们来看下向上维护的代码，只有几行，非常简单：
defmaintain(self):
#因为向上更新出现在插入元素之后，所以从最后一个位置开始维护
n=self._size-1
#cmp是自定义比较函数，用来自定义大顶堆还是小顶堆
whilen>0andself.cmp(self.items[n],self.items[(n-1)//2]):
#如果当前节点比父节点“大”，则交换
self.items[n],self.items[(n-1)//2]=self.items[(n-1)//2],self.items[n]
n=(n-1)//2
理解了堆的插入之后，那么堆的建立也应该很好理解了。所谓建堆的过程，其实就是将元素一个一个插入堆当中的过程。
我们利用maintain方法，很容易实现建堆的过程。
defpush(self,item):
ifself._size_limitisnotNoneandself._size>self._size_limit:
raiseIndexError('Heapisfull')
#array_size是数组的长度
#由于允许弹出元素，所以会导致数组的长度大于当前元素的数量的情况
ifself._size<self.array_size:
self.items[self._size]=item
self._size =1
#如果数组长度等于元素数量，那么append到数组末尾
else:
self.items.append(item)
self._size =1
self.array_size =1
#调用maintain，维护堆性质
self.maintain()
@staticmethod
defheapify(elements,min_or_max='min',compare_function=None):
#初始化，min_or_max表示是大顶堆还是小顶堆，允许传入自定义比较函数
heap=HeapQueue(min_or_max=min_or_max,compare_function=compare_function)
foriinelements:
heap.push(i)
returnheap
堆和其他数据结构不同，它对于数据的查询非常有限，只允许查询堆顶的元素。如果是大顶堆就是允许查询最大元素，否则则是允许查询最小元素。同样，也只允许删除堆顶的元素，由于删除堆顶的元素好像挤牙膏一样将元素挤出去一样，所以也称为“弹出”（pop）。
只是查询很好理解，我们返回数组下标为0的元素即可，但是如果是弹出该怎么办呢？弹出了之后，不是堆顶元素就空缺了吗？产生空缺了之后怎么办呢？
一种办法是从根节点的孩子当中选择一个作为替补顶上来，但是替补顶上之后又会产生新的空缺，这样一调整可能完全二叉树的性质就保不住了。所以只有一个办法，也很直观，就是将末尾的元素拿出来作为替补放到堆顶。但是显然末尾的元素不是最大的，所以这样操作之后还需要调整。
怎么调整呢？
当然是从堆顶开始将它和左右孩子进行比较，如果左右孩子当中存在比它大的，那么就交换，将这个元素往下传递。比如下图当中，我们弹出堆顶的元素100，根据算法的逻辑，我们会用末尾的7作为替补。
第一次我们将它和19与36进行比较，由于要满足大顶堆的性质，我们选择其中最大的36交换。于是我们将7往下传递到了原来36的位置，我们继续将它和两个孩子节点进行比较。我们发现25大于7，于是我们继续交换，这个时候到达了叶子节点，停止。
我们再反观维护之后的结果，仍然满足大顶堆的性质，并且仍然是一棵完全二叉树。和刚才插入时候的维护进行对比，我们会发现其实这整个过程是一个向下更新的过程。堆这个数据结构的核心其实就在这两个更新当中，在插入的时候向上更新，在弹出的时候向下更新。
代码也非常简单：
defpop(self):
front=self.items[0]
#弹出下标为0的节点之后，将末尾元素插入头部
self.items[0]=self.items[self._size-1]
self._size-=1
self.downward_maintain()
returnfront
defdownward_maintain(self):
n=0
whilen*2 1<self._size:
#计算左右孩子的下标
left_child=n*2 1
right_child=n*2 2
#判断左右孩子的大小关系，只会和其中大的发生交换
ifself.cmp(self.items[left_child],self.items[right_child]):
#如果左孩子大于右孩子也大于父节点，则交换
ifself.cmp(self.items[left_child],self.items[n]):
self.items[n],self.items[left_child]=self.items[left_child],self.items[n]
n=left_child
else:
break
#如果右孩子最大，也交换
elifself.cmp(self.items[right_child],self.items[n]):
self.items[n],self.items[right_child]=self.items[right_child],self.items[n]
n=right_child
else:
break
到这里，整个堆的主体部分就实现完了。整个过程还是比较直观的，并不复杂，只要记住了两个更新就足够了。
理解了堆之后我们再来看优先队列，我们使用优先队列的时候，希望每次取出优先级最大的数据，然后当我们填入数据的时候，队列会自动根据我们设置的优先级对数据进行排序。这不刚好就是堆的功能吗？所以通过堆，我们可以很方便地实现优先队列，当然我们没有必要这么做，因为在Python当中为我们封装了现成的堆，我们只需要调用它，就可以很轻松地自己封装一个优先队列。
importheapq
classPriorityQueue:
def__init__(self):
self._queue=[]
self._index=0
defpush(self,item,priority):
#传入两个参数，一个是存放元素的数组，另一个是要存储的元素，这里是一个元组。
#由于heap内部默认由小到大排，所以对priority取负数
heapq.heappush(self._queue,(-priority,self._index,item))
self._index =1
defpop(self):
returnheapq.heappop(self._queue)[-1]
如果你愿意，你还可以往这个类当中加入一些其他的辅助函数。当然，我还是建议大家，都能自己从头用堆实现一个属于自己的优先队列，体会一下亲手实现数据结构的成就感。
堆很实用，也不难写，希望大家都能体会到手撸数据结构的快乐。
今天的文章就到这里，原创不易，求个关注。
,
