二叉堆详解：从基本概念到代码实现
二叉堆详解：从基本概念到代码实现
二叉堆是一种重要的数据结构，广泛应用于优先队列和堆排序等场景。本文将从基本概念、性质、操作、代码实现到应用场景，全面解读二叉堆的原理和使用方法。
一、基本概念
二叉堆是一种特殊的完全二叉树，它满足堆性质：对于每个节点i，其子节点的值（或关键字）要么都小于等于节点i的值（称为最小堆），要么都大于等于节点i的值（称为最大堆）。二叉堆通常通过数组来实现，以便于存储和访问。
最大堆： 任何一个父节点都大于或等于它的左右子节点， 最大堆的最大元素再堆顶
最小堆: 任何一个父节点都小于或等于它的左右子节点，最小堆的最小元素再堆顶
二、性质
- 结构性质：二叉堆是一棵完全二叉树，除了最后一层外，其他层的节点都是满的，且最后一层的节点都靠左对齐。
- 堆性质：对于每个节点i，其子节点的值满足最小堆或最大堆的要求。
三、基本操作
插入（Insert）：向二叉堆中插入一个新元素。首先，将新元素添加到数组的末尾，然后通过上浮操作（percolate up）调整堆结构，以满足堆性质。
当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置。例如插入一个新节点，值是 0。
这时，新节点的父节点5比0大，显然不符合最小堆的性质。于是让新节点“上浮”，和父节点交换位置。
继续用节点0和父节点3做比较，因为0小于3，则让新节点继续“上浮”。
继续比较，最终新节点0“上浮”到了堆顶位置。
删除（Delete）：从二叉堆中删除一个元素。通常，我们删除堆顶元素（即数组的第一个元素），然后用数组的最后一个元素替换堆顶元素，并通过下沉操作（percolate down）调整堆结构。
二叉堆删除节点的过程和插入节点的过程正好相反，所删除的是处于堆顶的节点。例如删除最小堆的堆顶节点1。
这时，为了继续维持完全二叉树的结构，我们把堆的最后一个节点10临时补到原本堆顶的位置。
接下来，让暂处堆顶位置的节点10和它的左、右孩子进行比较，如果左、右孩子节点中最小的一个（显然是节点2）比节点10小，那么让节点10“下沉”。
继续让节点10和它的左、右孩子做比较，左、右孩子中最小的是节点7，由于10大于7，让节点10继续“下沉”。
这样一来，二叉堆重新得到了调整。
四、代码实现
class BinaryHeap:
def __init__(self, elements=None, max_heap=True):
"""
初始化二叉堆。
:param elements: 可选参数，一个列表，用于构建初始堆。
:param max_heap: 是否为最大堆，默认为True。
"""
self.heap = []
self.max_heap = max_heap
if elements:
for element in elements:
self.insert(element)
def parent(self, i):
"""
计算给定索引i的父节点索引。
:param i: 子节点的索引。
:return: 父节点的索引。
"""
return (i - 1) // 2
def left_child(self, i):
"""
计算给定索引i的左孩子节点索引。
:param i: 父节点的索引。
:return: 左孩子节点的索引。
"""
return 2 * i + 1
def right_child(self, i):
"""
计算给定索引i的右孩子节点索引。
:param i: 父节点的索引。
:return: 右孩子节点的索引。
"""
return 2 * i + 2
def swap(self, i, j):
"""
交换堆中索引为i和j的元素。
:param i: 第一个元素的索引。
:param j: 第二个元素的索引。
"""
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def sift_up(self, i):
"""
上浮操作，确保以i为根的子树满足堆的性质。
:param i: 子树根节点的索引。
"""
while i > 0:
parent_i = self.parent(i)
if (self.max_heap and self.heap[parent_i] < self.heap[i]) or \
(not self.max_heap and self.heap[parent_i] > self.heap[i]):
self.swap(parent_i, i)
i = parent_i
else:
break
def sift_down(self, i, heap_len):
"""
下沉操作，确保以i为根的子树满足堆的性质。
:param i: 子树根节点的索引。
:param heap_len: 堆的当前长度（元素数量）。
"""
largest = i
left = self.left_child(i)
right = self.right_child(i)
if left < heap_len and (
(self.max_heap and self.heap[left] > self.heap[largest]) or
(not self.max_heap and self.heap[left] < self.heap[largest])):
largest = left
if right < heap_len and (
(self.max_heap and self.heap[right] > self.heap[largest]) or
(not self.max_heap and self.heap[right] < self.heap[largest])):
largest = right
if largest != i:
self.swap(i, largest)
self.sift_down(largest, heap_len)
def insert(self, key):
"""
向堆中插入一个元素。
:param key: 要插入的元素。
"""
self.heap.append(key)
self.sift_up(len(self.heap) - 1)
def delete_max(self):
"""
删除并返回堆中的最大元素（对于最大堆）。
:return: 删除的元素。
"""
if not self.heap:
return None
if len(self.heap) == 1:
return self.heap.pop()
max_val = self.heap[0]
self.heap[0] = self.heap.pop()
self.sift_down(0, len(self.heap))
return max_val
if __name__ == '__main__':
b_heap = BinaryHeap([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], max_heap=False)
b_heap.insert(0)
print(b_heap.delete_max())
print(b_heap.delete_max())
五、应用场景
- 优先队列：二叉堆是实现优先队列的理想数据结构。在优先队列中，元素的优先级由它们的值决定。通过插入和删除操作，我们可以高效地添加和移除具有最高（或最低）优先级的元素。
- 堆排序：堆排序是一种基于二叉堆的排序算法。它首先构建一个最大堆，然后将堆顶元素与末尾元素交换，并将剩余元素重新调整为最大堆。重复这个过程，直到所有元素都排好序。堆排序的时间复杂度为O(nlogn)，且空间复杂度为O(1)。
六、总结
二叉堆是一种高效的数据结构，它利用堆性质实现了快速插入、删除和查找操作。在优先队列、堆排序等场景中，二叉堆发挥着重要作用。掌握二叉堆的实现和应用，对于提高算法效率和理解数据结构具有重要意义。