14 - 堆栈 - 小顶堆

**堆栈 - 小顶堆**

堆栈是一种特殊的数据结构，它遵循先进后出的原则。小顶堆是堆栈的一种特殊实现，所有元素都必须满足某个特定的比较规则。在本文中，我们将讨论小顶堆的定义、实现以及相关的算法。

**什么是小顶堆**

小顶堆是一种完全二叉树（Complete Binary Tree），其中每个节点的值都必须小于或等于其子节点的值。换句话说，父节点的值永远不会大于其子节点的值。这使得小顶堆成为一个非常有用的数据结构，特别是在需要频繁插入和删除元素的情况下。

**小顶堆的实现**

小顶堆可以使用数组或链表来实现。在本文中，我们将使用数组来实现小顶堆。我们将使用一个名为 `heap` 的数组来存储所有元素，每个元素都有一个索引 `i`，它表示该元素在堆中的位置。

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

def insert(self, value):
 self.heap.append(value)
 self._heapify_up(len(self.heap) -1)

def _heapify_up(self, i):
 while i >0:
 parent = (i -1) //2 if self.heap[parent] <= self.heap[i]:
 break self.heap[parent], self.heap[i] = self.heap[i], self.heap[parent]
 i = parent

def delete(self):
 if len(self.heap) ==0:
 return None if len(self.heap) ==1:
 return self.heap.pop()

 root = self.heap[0]
 self.heap[0] = self.heap.pop()
 self._heapify_down(0)
 return rootdef _heapify_down(self, i):
 while True:
 left_child =2 * i +1 right_child =2 * i +2 smallest = i if left_child < len(self.heap) and self.heap[left_child] < self.heap[smallest]:
 smallest = left_child if right_child < len(self.heap) and self.heap[right_child] < self.heap[smallest]:
 smallest = right_child if smallest == i:
 break self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
 i = smallest

min_heap = MinHeap()
min_heap.insert(5)
min_heap.insert(3)
min_heap.insert(8)
print(min_heap.delete()) # 输出:3print(min_heap.delete()) # 输出:5print(min_heap.delete()) # 输出:8