数据结构堆是线性结构嘛（堆是怎样的数据结构）

今天是算法和数据结构的第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]

如果你愿意，你还可以往这个类当中加入一些其他的辅助函数。当然，我还是建议大家，都能自己从头用堆实现一个属于自己的优先队列，体会一下亲手实现数据结构的成就感。

堆很实用，也不难写，希望大家都能体会到手撸数据结构的快乐。

今天的文章就到这里，原创不易，求个关注。