15 - 堆栈 - 大顶堆

**堆栈数据结构**

堆栈是一种线性数据结构，遵循后进先出(Last In First Out, LIFO)原则。它类似于一叠盘子，每次添加或删除元素都在顶部进行。

**大顶堆**

大顶堆是指堆栈中所有元素都是按照从大到小的顺序排列的。也就是说，堆栈中的每个元素都必须满足以下条件：

* 每个元素都必须大于或等于其子元素。
* 堆栈中的每个元素都必须是最大值。

**实现大顶堆**

要实现大顶堆，我们需要使用一个数组来存储堆栈中的元素。我们可以使用二叉树的方式来组织这些元素，使得父节点总是大于或等于其子节点。

下面是一个简单的例子，展示了如何在Python中实现大顶堆：

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

 def insert(self, value):
 # 将新元素添加到堆栈末尾 self.heap.append(value)
 # 如果堆栈中有多于一个元素，则需要调整堆栈，使得父节点总是大于或等于其子节点 if len(self.heap) >1:
 self._heapify_up(len(self.heap) -1)

 def _heapify_up(self, index):
 # 如果当前元素的父节点存在且小于当前元素，则交换它们 while index >0 and self.heap[index] > self.heap[(index -1) //2]:
 self.heap[index], self.heap[(index -1) //2] = self.heap[(index -1) //2], self.heap[index]
 index = (index -1) //2 def delete(self):
 # 如果堆栈中只有一个元素，则直接返回 if len(self.heap) ==1:
 return self.heap.pop(0)
 # 将堆栈中的最后一个元素移动到顶部 max_value = self.heap[0]
 self.heap[0] = self.heap.pop()
 # 如果堆栈中有多于一个元素，则需要调整堆栈，使得父节点总是大于或等于其子节点 if len(self.heap) >1:
 self._heapify_down(0)

 return max_value def _heapify_down(self, index):
 # 如果当前元素的左子节点存在且小于当前元素，则交换它们 while2 * index +1 < len(self.heap) and (self.heap[2 * index +1] > self.heap[index]):
 self.heap[index], self.heap[2 * index +1] = self.heap[2 * index +1], self.heap[index]
 index =2 * index +1 # 如果当前元素的右子节点存在且小于当前元素，则交换它们 while2 * index +2 < len(self.heap) and (self.heap[2 * index +2] > self.heap[index]):
 self.heap[index], self.heap[2 * index +2] = self.heap[2 * index +2], self.heap[index]
 index =2 * index +2# 测试max_heap = MaxHeap()
max_heap.insert(5)
max_heap.insert(3)
max_heap.insert(8)
max_heap.insert(4)
max_heap.insert(1)

print(max_heap.delete()) # 输出:8print(max_heap.delete()) # 输出:5print(max_heap.delete()) # 输出:4print(max_heap.delete()) # 输出:3print(max_heap.delete()) # 输出:1