赞同 0
分享

【数据结构】- 二叉堆

简介:二叉堆实现的本质就是完全二叉树,只是这个二叉树在物理存储上并非使用链表来存储元素,它使用的是顺序存储也就是列表/数组。其次,优先队列就是基于二叉堆实现的,这得益于二叉堆的`最大堆`和`最小堆`的特性。
  2021.04.20
  Bug Man
  0
  62
  172.17.0.1
  中国.上海
 
 

在文章概述我已经用最简短的语言形容了二叉堆的定位,二叉堆的特性就是最大堆最小堆,依靠这两个特性二叉堆每次取出最大最小的数据。在实现二叉堆之前有必要先了解一下二叉堆是如何做到这两个特性,又是如何做到维持本身的平衡保证每次都只拿最大最小的数据。

本文二叉堆讲解全部以最小堆举例,最小堆每一个父节点都必须比他的左右子节点要小,堆顶(根节点)必须是整棵树最小的元素。那么一个无序的完全二叉树怎么调整成为一个二叉堆呢?这里先提两个重要的概念:上浮下沉

先忽略怎么构建二叉堆,想象一下,给你一个已经存在的二叉堆,添加一个元素到堆底(也就是完全二叉树的最后一个元素的位置),看下面的树。将设,最右侧的-1是刚刚加入进去的一个元素,现在需要将这个元素上浮到合适的位置。

#        0
#    1       2
#  3   3   3   3
# 9 6 7 3 5 3 7 -1

这个时候拿到它的父节点3进行比较,如果3比-1大就交换位置,如果3的父节点2还比-1大继续交换位置,如果2的父节点0还比-1大就交换位置。这个过程就是上浮的过程,下面展示一下这个过程。

# 添加数据
#        0
#    1       2
#  3   3   3   3
# 9 6 7 3 5 3 7 -1

# 第一次判断上浮调整
#        0
#    1       2
#  3   3   3   -1
# 9 6 7 3 5 3 7 3

# 第二次判断上浮调整
#        0
#    1       -1
#  3   3   3   2
# 9 6 7 3 5 3 7 3

# 第三次判断上浮调整
#        -1
#    1       0
#  3   3   3   2
# 9 6 7 3 5 3 7 3

还是就刚才的这个二叉堆,现在需要获取它的最小元素,这个时候就拿掉他的堆顶(根节点,获取元素并从树中删除掉),将堆底元素临时放置在堆顶补充空缺。接下来开始操作下沉,当新堆顶元素3比左右子节点中最小的那个值要大,就与最小值交换位置(否则就与第二小的交换位置),这个时候是0;第二次判断左右子节点3和2,其中2最小且比父元素3要小就与2交换位置,到这个时候再往下沉已经不满足条件无法下沉了。

# 获取最小值之后堆
#        3
#    1       0
#  3   3   3   2
# 9 6 7 3 5 3 7 

# 第一次判断下沉
#        0
#    1       3
#  3   3   3   2
# 9 6 7 3 5 3 7

# 第二次判断下沉
#        0
#    1       2
#  3   3   3   3
# 9 6 7 3 5 3 7

上面已经展示了上浮下沉的逻辑与应用,这个时候就可以依靠这个下沉来构建二叉堆了,就是将一个不满足条件的二叉树非叶子结点依次下沉就可以达到调整成为二叉堆的目的。还有一个重点就是怎么使用Python中的list列表来构建二叉堆,这里就需要借用到两个公式:left_children = (parent_children * 2) + 1right_children = (parent_children * 2) + 2。现在可以看下面的实现代码了,如果还有不清楚的可以上网去搜索二叉堆的实现原理(每个人的代码可能都不一样)。

import math
from copy import deepcopy


class BinaryHeap(object):

    def __init__(self):
        """ 二叉堆初始化 """
        self.heapList = list()
        self.heapSize = 0

    def insert(self, element: int) -> None:
        """ 插入元素 """
        # 将新的元素追加到堆底(列表最后的位置)
        self.heapList.append(element)
        self.heapSize += 1
        # 进行上浮将元素放置在合适的位置
        self.__come_up()

    def build_heap(self, heap: list) -> None:
        """ 构建二叉堆 """
        self.heapSize = len(heap)
        self.__build_heap(heap)

    def get_element(self) -> int:
        """ 获取堆顶元素 """
        element = self.heapList[0]
        return element

    def pop_element(self) -> int:
        """ 获取并删除堆顶元素 """
        element = self.heapList[0]
        # 用堆底元素暂时替代堆顶元素
        self.heapList[0] = self.heapList.pop(-1)
        self.heapSize -= 1
        # 将堆顶元素下沉至合适的位置
        self.__come_down()
        return element

    def __come_up(self) -> None:
        """ 堆底元素上浮 """
        children_index = self.heapSize - 1
        parent_index = (children_index - 1) // 2
        # 堆底元素(留作单向赋值最后使用)
        temp = self.heapList[children_index]
        # 父级在有效范围内 且 子元素比父元素小时 单向赋值
        while parent_index >= 0 and temp < self.heapList[parent_index]:
            self.heapList[children_index] = self.heapList[parent_index]
            children_index = parent_index
            parent_index = (parent_index - 1) // 2
        # 单项覆盖最后决定堆底元素位置
        self.heapList[children_index] = temp

    def __come_down(self, index: int = 0) -> None:
        """ 堆顶元素下沉 """
        if not self.heapList:
            return
        parent_index = index
        children_index = (parent_index * 2) + 1
        temp = self.heapList[parent_index]
        # 子节点在有效范围内 且 子节点小于父节点
        while children_index < self.heapSize and self.heapList[children_index] < temp:
            # 选择左右子节点最小的交换位置
            if children_index + 1 < self.heapSize:
                if self.heapList[children_index+1] < temp and self.heapList[children_index+1] < self.heapList[children_index]:
                    children_index = children_index + 1
            self.heapList[parent_index] = self.heapList[children_index]
            parent_index = children_index
            children_index = (children_index * 2) + 1
        # 单项覆盖最后决定堆顶元素位置
        self.heapList[parent_index] = temp

    def __build_heap(self, heap: list):
        """ 构建二叉堆 """
        index = int((len(heap) - 2) // 2)
        self.heapList = heap
        while index >= 0:
            self.__come_down(index)
            index -= 1

    def render_heap(self) -> None:
        """ 渲染二叉堆 """
        # 计算以2为底,二叉树元素+1个的对数(满二叉树元素个数 = (2 ^ 深度) - 1)
        depth = math.log(self.heapSize + 1, 2)
        # 如果不为整数加一层
        remainder = depth % 1
        if remainder != 0:
            depth = depth + 1
        depth = int(depth)
        # 初始化头部空格列表
        depth_list = list()
        # 计算堆底满叶结点个数
        full_node = int(math.pow(2, depth) // 2)
        for d in range(depth):
            current_count = int(math.pow(2, d))
            depth_list.append([' '] * int((full_node // current_count) - 1))
        # 遍历二叉堆
        render_list = list()
        children_index = [0]
        queue = [self.heapList[0]]
        per_interval = 0
        while children_index and children_index[-1] < self.heapSize:
            # 暂时获取当前层下标列表
            current_row = deepcopy(depth_list[0])
            # 循环处理当前队列中数据,直至队列为空
            while queue:
                temp = queue.pop(0)
                current_row.append(str(temp))
                current_row.append(' ' * per_interval)
            render_list.append(current_row)
            temp_index = list()
            # 遍历获取当前层的所有左右子节点下标,取出并存储到队列;获取左右子节点存储到新的列表中,下次循环使用。
            for index in children_index:
                left_children = (index * 2) + 1
                if left_children < self.heapSize:
                    queue.append(self.heapList[left_children])
                    temp_index.append(left_children)
                right_children = (index * 2) + 2
                if right_children < self.heapSize:
                    queue.append(self.heapList[right_children])
                    temp_index.append(right_children)
            children_index = temp_index
            # 删除当前层列表,并记录当前层头部空格个数(为下一行间隔数)
            per_interval = len(depth_list.pop(0))
        # 遍历最终结果
        for render in render_list:
            print(''.join(render))


if __name__ == '__main__':
    b_h = BinaryHeap()
    b_h.insert(0)
    b_h.insert(1)
    b_h.insert(5)
    b_h.insert(6)
    b_h.insert(7)
    b_h.insert(2)
    b_h.insert(7)
    b_h.insert(9)
    b_h.insert(3)
    b_h.insert(3)
    b_h.insert(3)
    b_h.insert(3)
    b_h.insert(3)
    b_h.insert(3)
    b_h.insert(3)
    print(b_h.heapList)
    b_h.render_heap()
    b_h.pop_element()
    print(b_h.heapList)
    b_h.render_heap()
    # [0, 1, 2, 3, 3, 3, 3, 9, 6, 7, 3, 5, 3, 7, 3]
    #        0
    #    1       2
    #  3   3   3   3
    # 9 6 7 3 5 3 7 3
    # [1, 3, 2, 3, 3, 3, 3, 9, 6, 7, 3, 5, 3, 7]
    #        1
    #    3       2
    #  3   3   3   3
    # 9 6 7 3 5 3 7
    # 构建二叉堆
    # b_h.build_heap([8, 5, 7, 3, 4, 1, 9, 6, 5, 0])
    # print(b_h.heapList)
    # b_h.render_heap()
    # [0, 3, 1, 5, 4, 7, 9, 6, 8, 5]
    #        0
    #    3       1
    #  5   4   7   9
    # 6 8 5