在文章概述我已经用最简短的语言形容了二叉堆的定位,二叉堆的特性就是最大堆
和最小堆
,依靠这两个特性二叉堆每次取出最大
或最小
的数据。在实现二叉堆之前有必要先了解一下二叉堆是如何做到这两个特性,又是如何做到维持本身的平衡保证每次都只拿最大
或最小
的数据。
本文二叉堆讲解全部以最小堆举例,最小堆每一个父节点都必须比他的左右子节点要小,堆顶(根节点)必须是整棵树最小的元素。那么一个无序的完全二叉树怎么调整成为一个二叉堆呢?这里先提两个重要的概念:上浮
和下沉
。
先忽略怎么构建二叉堆,想象一下,给你一个已经存在的二叉堆,添加一个元素到堆底(也就是完全二叉树的最后一个元素的位置),看下面的树。将设,最右侧的-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) + 1
和right_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