聊聊堆Heap和二叉堆的实现和特性

聊聊堆Heap和二叉堆的实现和特性

堆 Heap

Heap：可以迅速找到一堆数中的最大或者最小值的数据结构。

将根节点最大的堆叫做大顶堆或大根堆，根节点最小的堆叫做小顶堆或小根堆。

常见的堆有二叉堆、裴波那契堆等。

堆本身是一个相对比较抽象的数据结构，那么它有具体的实现就分为二叉堆(二项堆、Binary)、裴波那契堆(基于树的)。那么要实现的话一般面试来说或者经常会用的话就是二叉堆来实现，当然在工业级比较牛逼的应用都是裴波那契以及非常严格裴波那契。裴波那契堆因为相对比较复杂，你可以不知道去怎么实现，但是你可以看它的时空复杂度更好，它的实现也是基于树，但是并不少二叉树而是多叉的。

假设是大顶堆，则常见操作(API):

find-max：O(1)delete-max：O(logN)insert(create)：O(logN) or O(1)

“堆” 这种数据结构为什么会有用? 在很多线上中的情形经常会在使用，比如说经常一个数一个数的过来，同时还有从另外一边的化经常去删除一些数据，问你这些数据里面它最大值是多少?这里的最大值可能就代表优先级最高的结点或者是那个数需要你先处理的，比如说你的任务流里面随时你要拿出优先级最高的任务优先处理，那么这种数据结构就更加的好用。

有些人可能会想我用数组来实现可不可以?或者是我直接排序可不可以?这里我们可以思考一下： 假设维护一个数组，每次有个新元素插入进来，你就需要把整个数组进行一次所谓的排序，这样的话时间复杂度就会是 nlogn，这样的话就是不够高效的，另外删除也可能比较麻烦，假设删除的是最大值或最小值在最后面的话还好，可以是 O(1) 的时间复杂度，但是如果在最前面的话，你就必须把整个数组最前面元素删除掉之后，把整个数组往前挪，这样时间复杂度又变差了。

当你提到“堆” 的时候，不要默认认为是二叉堆，同时你要知道堆的实现又很多种，而二叉堆本身的话只是因为它相对比较容易实现，它的时间效率是堆里面算比较差的。

二叉堆的性质

通过完全二叉树来实现(注意：不是二叉搜索树);

什么是完全二叉树? 就是它的根和每一级结点都是满的，除了最下面一层叶子结点可能不满之外，其他上面结点都是满的。

二叉堆(大顶)它满足下列性质：

性质1：是一颗完全树;性质2：树中任意结点的值总数 >= 其子节点的值;

由于性质2，就可以保证根结点是最大的结点，所以我们访问最大值就直接返回这个根结点值。这里思考一个问题：为什么要做成树的结构呢?其实就要方便，因为找最大值是O(1)了是满足的，但是问题是后续你要删除一个元素或者你要添加一个元素，怎么让这个操作高效，至少是 logn 的。

二叉堆的实现细节

二叉堆一般都通过 “数组” 来实现假设“第一个元素” 在数组中的索引为 0 的话，则父结点和子结点的位置关系如下：索引为 i 的左孩子的索引是 (2∗i+1);索引为 i 的右孩子的索引是 (2∗i+2);索引为 i 的父结点的索引是 floor((i−1)/2);

因为把一个完全二叉树依次放到一维数组里面去，那么它的孩子和父亲之间的关系，就可以直接用下班的数学关系表示了。

Insert 插入操作

新元素一律先插入到堆的尾部依次向上调整整个堆的结构(一直到根即可) HeapifyUp

当这个堆要进行维护操作，也就是插入元素的时候以及你要删除元素的时候要怎么做?

例子：85 添加到二叉堆中

操作的细节分为两步：

第一步：首先把新元素插入到堆的尾部再说;(新的元素可能是特别大或者特别小，那么要做的一件事情就是重新维护一下堆的所有元素，把新元素挪到这个堆的相应的位置)第二步：依次向上调整整个堆的结构，就叫 HeapifyUp

85 按照上面讲的先插入到堆的尾部，也就是一维数组的尾部，一维数组的尾部的话就上图的位置，因为这是一个完全二叉树，所以它的尾部就是50后面这个结点。插进来之后这个时候就破坏了堆，它的每一个结点都要大于它的儿子的这种属性了，接下来要做的事情就是要把 85 依次地向上浮动，怎么浮动?就是 85 大于它的父亲结点，那么就和父亲结点进行交换，直到走到根如果大于根的话，就和根也进行交换。

85 再继续往前走之后，它要和 80 再进行比较，同理可得：也就是说这个结点每次和它的父亲比，如果它大于它的父亲的话就交换，直到它不再大于它的父亲。

Delete Max 删除堆顶操作

将堆尾元素替换到顶部(即堆顶被替代删除掉)

依次从根部向下调整整个堆的结构(一直到堆尾即可) HeapifyDown

例子：90 从二叉堆中删除

堆的实现代码模版

Java 版本

C/C++ 版本

Javascript 版本

Python 版本

Python import sys  class BinaryHeap:         def __init__(self, capacity):          self.capacity = capacity          self.size = 0         self.Heap = [0]*(self.capacity + 1)          self.Heap[0] = -1 * sys.maxsize          self.FRONT = 1        def parent(self, pos):          return pos//2        def leftChild(self, pos):          return 2 * pos         def rightChild(self, pos):          return (2 * pos) + 1        def isLeaf(self, pos):          if pos >= (self.size//2) and pos <= self.size:              return True         return False        def swap(self, fpos, spos):          self.Heap[fpos], self.Heap[spos] = self.Heap[spos], self.Heap[fpos]         def heapifyDown(self, pos):             if not self.isLeaf(pos):              if (self.Heap[pos] > self.Heap[self.leftChild(pos)] or                 self.Heap[pos] > self.Heap[self.rightChild(pos)]):                     if self.Heap[self.leftChild(pos)] < self.Heap[self.rightChild(pos)]:                      self.swap(pos, self.leftChild(pos))                      self.heapifyDown(self.leftChild(pos))                     else:                      self.swap(pos, self.rightChild(pos))                      self.heapifyDown(self.rightChild(pos))         def insert(self, element):          if self.size >= self.capacity :              return         self.size+= 1         self.Heap[self.size] = element             current = self.size             while self.Heap[current] < self.Heap[self.parent(current)]:              self.swap(current, self.parent(current))              current = self.parent(current)         def Print(self):          for i in range(1, (self.size//2)+1):              print(" PARENT : "+ str(self.Heap[i])+" LEFT CHILD : "+                                  str(self.Heap[2 * i])+" RIGHT CHILD : "+                                 str(self.Heap[2 * i + 1]))          def minHeap(self):             for pos in range(self.size//2, 0, -1):              self.heapifyDown(pos)         def delete(self):             popped = self.Heap[self.FRONT]          self.Heap[self.FRONT] = self.Heap[self.size]          self.size-= 1         self.heapifyDown(self.FRONT)          return popped      def isEmpty(self):         return self.size == 0              def isFull(self):          return self.size == self.capacity if __name__ == "__main__":             print('The minHeap is ')      minHeap = BinaryHeap(5)     minHeap.insert(5)      minHeap.insert(3)      minHeap.insert(17)      minHeap.insert(10)      minHeap.insert(84)      minHeap.insert(19)      minHeap.insert(6)      minHeap.insert(22)      minHeap.insert(9)      minHeap.minHeap()         minHeap.Print()      print("The Min val is " + str(minHeap.delete()))

高频题目

总结

注意：二叉堆只是堆的一种实现形式，二叉堆为什么出现得多?是因为它较为常见且简单，但是它并不是最优的实现，正是因为这个原因，所以二叉堆很多时候并不是完全的那么实用，那么如果在工程的代码里面我们可以直接调 优先队列(priority_queue) 就行了。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。