数据结构——堆

**数据结构——堆**

堆是一种特殊的二叉树，满足以下条件：

1. **完全性**: 堆是一个完全二叉树，这意味着除去根结点外，每个父结点都有两个子结点。
2. **最小值或最大值**: 根据堆的类型，它可以是最小堆（每个父结点的值小于或等于其子结点）或最大堆（每个父结点的值大于或等于其子结点）。

**堆的应用**

堆有许多实用的应用，例如：

1. **优先队列**: 堆可以用来实现优先队列，这是一种数据结构，它允许你快速找到最小或最大元素。
2. **排序算法**: 堆可以用来实现一些高效的排序算法，如堆排序。
3. **任务调度**: 堆可以用来实现任务调度系统，例如在多线程环境中。

**堆的类型**

根据堆的结构，可以分为以下几种：

1. **二叉堆**: 这是最常见的一种堆，它是一棵完全二叉树。
2. **斐波那契堆**: 这种堆使用斐波那契数列来表示其高度。

**堆的操作**

堆支持以下几种基本操作：

1. **插入**: 将一个新元素添加到堆中。
2. **删除最小或最大值**: 移除堆顶元素，并返回其值。
3. **peek**: 返回堆顶元素的值，但不移除它。

**实现堆**

下面是一个简单的堆实现，使用二叉树结构：

class Heap:
 def __init__(self):
 self.heap = []

 def insert(self, value):
 # 将新元素添加到堆中 self.heap.append(value)
 self._heapify_up(len(self.heap) -1)

 def delete_min(self):
 # 移除最小值，并返回其值 if len(self.heap) ==0:
 return None min_value = self.heap[0]
 self.heap[0] = self.heap[-1]
 self.heap.pop()
 self._heapify_down(0)
 return min_value def peek_min(self):
 # 返回最小值，但不移除它 if len(self.heap) ==0:
 return None return self.heap[0]

 def _heapify_up(self, index):
 # 将元素向上堆化 parent_index = (index -1) //2 if index >0 and self.heap[parent_index] > self.heap[index]:
 self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
 self._heapify_up(parent_index)

 def _heapify_down(self, index):
 # 将元素向下堆化 left_child_index =2 * index +1 right_child_index =2 * index +2 smallest = index if (
 left_child_index < len(self.heap)
 and self.heap[left_child_index] < self.heap[smallest]
 ):
 smallest = left_child_index if (
 right_child_index < len(self.heap)
 and self.heap[right_child_index] < self.heap[smallest]
 ):
 smallest = right_child_index if smallest != index:
 self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
 self._heapify_down(smallest)

# 测试堆heap = Heap()
heap.insert(5)
heap.insert(3)
heap.insert(8)
print(heap.peek_min()) # 输出:3print(heap.delete_min()) # 输出:3print(heap.peek_min()) # 输出:5