模拟实现优先级队列(堆)

**模拟实现优先级队列（堆）**

在计算机科学中，优先级队列是一种数据结构，它允许我们快速地插入或删除元素，同时保持元素的顺序按照某个优先级来排序。这种数据结构非常有用，在许多算法和应用程序中，如任务调度、缓存管理等。

在本文中，我们将模拟实现一个优先级队列（堆），使用 Python语言来编写代码示例。

**什么是堆？**

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

1. 每个结点都有一个值。
2. 对于任何结点，所有它的子结点的值都大于或等于它本身的值（对于最大堆），或者小于等于它本身的值（对于最小堆）。
3. 根结点是树中最大的（或最小）元素。

**实现优先级队列**

我们将使用一个列表来模拟堆。每个元素都有一个索引，表示它在列表中的位置。

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

def insert(self, value):
 # 将新元素添加到列表末尾 self.heap.append(value)
 # 将新元素向上移动到正确的位置 self._heapify_up(len(self.heap) -1)

# 将元素向上移动到正确的位置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 delete(self):
 # 将最后一个元素作为根结点 root = self.heap[0]
 # 将最后一个元素移到列表末尾 self.heap[0] = self.heap.pop()
 # 将根结点向下移动到正确的位置 self._heapify_down(0)
 return root# 将元素向下移动到正确的位置def _heapify_down(self, index):
 left_child_index =2 * index +1 right_child_index =2 * index +2 largest_index = index if left_child_index < len(self.heap) and self.heap[left_child_index] > self.heap[largest_index]:
 largest_index = left_child_index if right_child_index < len(self.heap) and self.heap[right_child_index] > self.heap[largest_index]:
 largest_index = right_child_index if largest_index != index:
 # 交换最大元素和当前元素 self.heap[index], self.heap[largest_index] = self.heap[largest_index], self.heap[index]
 # 继续向下移动 self._heapify_down(largest_index)

pq = PriorityQueue()

# 插入元素pq.insert(5)
pq.insert(3)
pq.insert(8)
pq.insert(1)

# 删除元素print(pq.delete()) # 输出:8# 删除元素print(pq.delete()) # 输出:5# 删除元素print(pq.delete()) # 输出:3# 删除元素print(pq.delete()) # 输出:1