优先队列的核心,面试的常客,带你深入了解堆

本文始发于个人公众号:TechFlow,原创不易,求个关注

今天是算法和数据结构的第21篇,我们来聊一个新的数据结构——(heap)。

和链表、二叉树以及数组这些热门的数据结构相比,堆相对比较冷门。如果你对数据结构了解不深的话,可能很少听说。但是我们经常用到它,虽然可能你并不一定能感知到。比如说优先队列,我们就经常使用。我们需要用到这样一个数据结构,能够根据我们存入数据的优先级进行排序,将优先级高的排在前面。在和调度相关的一些系统和算法当中,优先队列是必然会用到的。但是很少有人知道,优先队列说是一个队列,但其实是通过堆实现的。

那么堆究竟是一个怎样的数据结构呢?

堆的定义

堆的实质其实是二叉树,并且还不是一般的二叉树,而是比较特别的二叉树。

特别在什么地方呢,在于这棵二叉树除了叶子之外的所有节点都是“满”的。所谓的满,也就是没有空缺的意思。

从上图当中我们可以看到,如果去掉最后一层,那么这棵二叉树就是全满的。最后一层叶子节点也是有要求的,要求叶子节点都靠左对齐。满足这两个条件的二叉树成为完全二叉树(complete binary tree)。这个概念如果记不住也没有关系,我好像也只在堆当中遇到。

堆是完全二叉树,但是显然不是所有的完全二叉树都是堆,堆还有一个特殊的性质,就是大小的传递性

堆根据大小传递性的不同分为大顶堆和小顶堆,所谓的大顶堆就是堆顶的元素也就是树根的元素是最大的。如果是小顶堆则相反,堆顶元素是最小的。所以这两者基本一样,我们就以大顶堆举例。这个传递性其实很好理解,其实只有一条,就是所有节点的值大于它两个孩子的值。也就是说从树根到树叶每一条路径都是递减的。

我们可以看下这张图:

img
img

100有两个孩子节点,19和36,100比19和36都大。19有两个孩子17和3,19比它们都大。这应该是很好理解的,堆巧妙的点在哪里呢,巧妙的点在于我们可以用数组来存储这个结构,而不需要自己建树。用数组存储的方法也很简单,我们给图上的点标上下标,可以得到:

image-20200520203331364
image-20200520203331364

我们找下规律,可以发现对于一个树上的一个节点,假设它在数组当中的下标是i的话。那么它的左孩子的下标是i * 2 + 1, 它的右孩子下标为i * 2 + 2,它的父节点是(i – 1) // 2。

有了这个规律之后,我们只要知道某个点的坐标,就可以知道它的父亲和两个孩子的坐标。这也是用数组来存储堆非常巧妙和方便的点。

堆的插入

有了这个性质有什么用呢?其实很有用,我们可以利用它非常方便地完成堆的维护。

想象一下,首先,往堆的末尾插入元素并不会破坏完全二叉树这个性质。因为完全二叉树的叶子节点是往左对齐的,我们插入元素必然也是在最左边,所以不管我们插入的元素数值是多大,这都不会影响完全二叉树这个性质。但是显然,我们插入的数值大小会影响堆结构的正确性,比如如果我们插入9,插入的位置就不满足大顶堆的性质了。

image-20200520203932970
image-20200520203932970

这个时候,为了维护堆的性质我们需要调整当中的数据。所以其实堆插入元素的过程就是一个调整顺序的过程,那怎么调整呢,其实很简单,就是将我们插入的元素向上比较,如果它比它的父节点元素更大,那么就将它和父节点进行交换,一直到它小于父节点或者是它称为堆顶为止。

假如说,我们插入的元素不是9,而是105,那么最后得到的结果应该是这样的:

image-20200520204847608
image-20200520204847608

这个就是堆的插入过程,因为我们只有插入的位置可能会导致破坏堆结构,所以我们只需要从插入的位置开始往上维护即可。其余的位置并不会影响,并且对于整个这条链路上可能会被影响的节点而言,它们只可能变大,不可能减小,因此也不会出现交换了之后有新的不满足堆性质的情况产生。

由于这个插入的过程是自下而上的,因此整个过程也被称为是向上更新

我们来看下向上维护的代码,只有几行,非常简单:

def maintain(self):
   # 因为向上更新出现在插入元素之后,所以从最后一个位置开始维护
    n = self._size - 1
    # cmp是自定义比较函数,用来自定义大顶堆还是小顶堆
    while n > 0 and self.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方法,很容易实现建堆的过程。

   def push(self, item):
        if self._size_limit is not None and self._size > self._size_limit:
            raise IndexError('Heap is full')
        
        # array_size是数组的长度
        # 由于允许弹出元素,所以会导致数组的长度大于当前元素的数量的情况
        if self._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
    def heapify(elements, min_or_max='min', compare_function=None):
       # 初始化, min_or_max表示是大顶堆还是小顶堆,允许传入自定义比较函数
        heap = HeapQueue(min_or_max=min_or_max, compare_function=compare_function)
        for i in elements:
            heap.push(i)
        return heap

堆的查询与弹出

堆和其他数据结构不同,它对于数据的查询非常有限,只允许查询堆顶的元素。如果是大顶堆就是允许查询最大元素,否则则是允许查询最小元素。同样,也只允许删除堆顶的元素,由于删除堆顶的元素好像挤牙膏一样将元素挤出去一样,所以也称为“弹出”(pop)。

只是查询很好理解,我们返回数组下标为0的元素即可,但是如果是弹出该怎么办呢?弹出了之后,不是堆顶元素就空缺了吗?产生空缺了之后怎么办呢?

一种办法是从根节点的孩子当中选择一个作为替补顶上来,但是替补顶上之后又会产生新的空缺,这样一调整可能完全二叉树的性质就保不住了。所以只有一个办法,也很直观,就是将末尾的元素拿出来作为替补放到堆顶。但是显然末尾的元素不是最大的,所以这样操作之后还需要调整。

怎么调整呢?

当然是从堆顶开始将它和左右孩子进行比较,如果左右孩子当中存在比它大的,那么就交换,将这个元素往下传递。比如下图当中,我们弹出堆顶的元素100,根据算法的逻辑,我们会用末尾的7作为替补。

image-20200520210941652
image-20200520210941652

第一次我们将它和19与36进行比较,由于要满足大顶堆的性质,我们选择其中最大的36交换。于是我们将7往下传递到了原来36的位置,我们继续将它和两个孩子节点进行比较。我们发现25大于7,于是我们继续交换,这个时候到达了叶子节点,停止。

我们再反观维护之后的结果,仍然满足大顶堆的性质,并且仍然是一棵完全二叉树。和刚才插入时候的维护进行对比,我们会发现其实这整个过程是一个向下更新的过程。堆这个数据结构的核心其实就在这两个更新当中,在插入的时候向上更新,在弹出的时候向下更新

代码也非常简单:

    def pop(self):
        front = self.items[0]
       # 弹出下标为0的节点之后,将末尾元素插入头部
        self.items[0] = self.items[self._size-1]
        self._size -= 1
        self.downward_maintain()
        return front

    def downward_maintain(self):
        n = 0
        while n * 2 + 1 < self._size:
           # 计算左右孩子的下标
            left_child = n * 2 + 1
            right_child = n * 2 + 2
            # 判断左右孩子的大小关系,只会和其中大的发生交换
            if self.cmp(self.items[left_child], self.items[right_child]):
               # 如果左孩子大于右孩子也大于父节点,则交换
                if self.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
            # 如果右孩子最大,也交换
            elif self.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当中为我们封装了现成的堆,我们只需要调用它,就可以很轻松地自己封装一个优先队列。

import heapq

class PriorityQueue:
  
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        # 传入两个参数,一个是存放元素的数组,另一个是要存储的元素,这里是一个元组。
        # 由于heap内部默认由小到大排,所以对priority取负数
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

如果你愿意,你还可以往这个类当中加入一些其他的辅助函数。当然,我还是建议大家,都能自己从头用堆实现一个属于自己的优先队列,体会一下亲手实现数据结构的成就感。如果你想要参考我的代码,可以在公众号内回复“”,我把我的代码发给你。

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

今天的文章就到这里,原创不易,扫码关注我,获取更多精彩文章。