如何使用优先队列或堆实现栈？

栈是编程和计算机科学中广泛使用的基本数据结构。元素按照后进先出 (LIFO) 原则从栈的顶部添加和删除。尽管优先队列或堆通常使用动态数组或链表构建，但它们可以有效地实现栈。在这些实现中，新项目具有更高的优先级，因为元素根据其插入顺序进行优先级排序。通过这样做，项目遵循栈的基本行为，并以 LIFO 顺序从优先队列或堆中出现。本文解释了如何创建一个简单的栈，该栈可以通过使用优先队列或堆以 O(log n) 的步骤高效执行。

栈、优先队列和最小堆

让我们回顾一下栈、优先队列和堆的概念。在这种情况下，我们将使用最小堆。

栈

• 线性数据结构模拟了一个真实的栈，具有两个主要操作——push 和 pop。
• Push 将一个元素添加到栈的顶部。Pop 从顶部移除元素。
• 栈遵循 LIFO（后进先出）顺序，这意味着最近添加的元素最先被移除。
• 栈具有抽象数据类型，其关键函数包括 push()、pop()、peek() 和 isEmpty()。
• 它们通常使用数组或链表实现。索引或指针跟踪顶部元素。
• 应用包括撤消/重做功能、用于匹配括号的编译器语法检查以及浏览器后退/前进导航。

优先队列

• 优先队列是一种抽象数据类型，类似于普通队列，但每个元素都有一个优先级值。
• 元素按优先级顺序出队——高优先级元素先于低优先级元素。
• 优先队列需要两个关键操作——插入（入队）和移除/访问最高优先级（出队）。
• 优先队列通常使用堆实现，堆提供对数时间操作。
• 堆中的元素按其自然顺序或自定义比较器排序。
• 应用包括任务调度、Dijkstra 等算法以及查找最小生成树。

最小堆

• 最小堆是一个完整的二叉树，它满足堆属性——每个节点的值都小于或等于其子节点。
• 根节点包含树中的最小值。元素可以以对数时间高效地入队和出队。
• 最小堆有效地实现了优先队列所需的各种操作。
• 关键操作包括 peek（获取最小值）、insert（插入）、extractMin（移除最小值）和 decrease key（减小键值）。
• 最小堆通常使用数组实现。子节点和父节点之间存在数学关系。
• 用于实现优先队列、Dijkstra 等图算法以及堆排序等排序算法。

使用优先队列和最小堆实现栈相较于普通数组和链表的优势

效率

• 使用最小堆或优先队列，基本的栈操作（如 push 和 pop）可以在 O(log n) 时间内实现。与数组和链表的 O(1) 时间相比，这是一个显著的效率提升。
• 堆结构为插入和删除提供了对数时间复杂度。堆属性只需要冒泡上浮/下沉操作。
• 尽管对数时间略慢于常数时间，但它在大多数应用中表现出色。搜索 log n 个元素仍然非常快。
• 堆比数组更高效，因为不需要重新调整大小或复制元素。无需分配额外容量。

灵活性

• 优先队列允许元素以任何优先级顺序插入，而不仅仅是像栈那样的 LIFO 顺序。这提供了更大的灵活性。
• 可以实现自定义比较器以根据应用程序特定标准而不是自然顺序对元素进行排序。
• 堆本质上实现了优先级排序并提供了一个抽象数据类型。实现细节是隐藏的。
• 与数组不同，堆操作（如 push/pop）不需要直接访问索引或特定元素。

内存使用

• 堆只需要一个数组（加上少量簿记变量）即可实现优先队列。内存效率非常高。
• 不需要像链表那样分配 next/previous 指针。每个元素的开销较低。
• 堆数据结构将元素整合在一个基于数组的密集结构中。内存分配更集中。
• 堆优先队列的空间复杂度为 O(n)，与数组/链表的 O(n) 相同。但常数因子更低。

可重用性

• 堆代码可以跨需要优先队列功能的应用程序重用，因为它是一个抽象数据类型。
• 堆用于 Dijkstra 等算法，因此一个实现可以服务于多种目的。
• 将堆逻辑封装到单独的类中可以促进跨项目的可重用性。
• 优先队列是标准化的数据结构，因此堆的实现将可移植到不同的语言。

如何实现栈？

算法

1. 创建一个最小堆或优先队列数据结构来存储栈元素。
2. 创建一个空的最小堆/优先队列来初始化一个空栈。
3. 要将元素推入栈中，将元素插入堆/优先队列。优先级根据元素的插入顺序设置（新元素具有更高的优先级）。
4. 要从栈中弹出一个元素，从堆/优先队列中删除并返回最高优先级的元素。这将删除最近添加的元素。
5. 要查看顶部元素，返回堆/优先队列中最高优先级的元素而不将其删除。
6. 检查堆/优先队列是否为空以实现栈的 isEmpty()。

方法

• 使用最小堆根据插入顺序优先级高效地实现优先队列。
• 使用数组表示堆中的元素。通过数学计算父/子节点的索引。
• 编写用于插入的 siftUp、用于删除的 siftDown 和用于获取最小值的 peek 辅助方法。
• 使用 siftUp 入队，使用 siftDown 出队以保持最小堆有序。
• 独立于元素跟踪优先级/插入计数以分配优先级。
• 将堆封装在一个带有公共 push/pop/peek 方法的优先队列/栈类中。
• 如果排序比插入顺序更复杂，请使用可比较接口或自定义比较器。
• 如果需要大型栈，请考虑容量限制、动态调整大小和其他优化。
• 编写单元测试以验证 LIFO 行为和边缘情况。

输出

Python 程序说明

MinHeap 类

• __init__() 使用索引 0 处的虚拟元素初始化底层堆列表。这简化了子/父计算。大小设置为 0。
• __swap__() 是一个辅助方法，用于按索引交换堆列表中的两个元素。冒泡操作使用此方法。
• __push__() 接收一个项目，将其附加到堆列表，增加大小，并调用 __bubbleUp() 以维护堆顺序。插入逻辑由 __bubbleUp() 处理。
• __pop__() 存储根元素，用最后一个元素替换根，减小大小，弹出最后一个元素，然后将新根冒泡下沉。删除逻辑在 __bubbleDown() 中。
• __peek__() 只需在常数时间内返回索引 1 处的根元素。
• __bubbleUp__() 递归地将插入的元素与其父元素进行比较，如果小于父元素则交换。这会使元素向上渗透到正确的位置。
• __bubbleDown__() 将根元素与其子元素进行比较，与较小的子元素交换。递归重复以冒泡下沉到正确的位置。

Stack 类

• __init__() 初始化一个空的 MinHeap 来存储栈元素。
• __push__() 调用堆的 push() 方法进行插入，同时保持最小堆排序。
• __pop__() 调用堆的 pop() 方法，该方法移除最小元素。这会移除最近添加的元素，就像栈一样。
• __peek__() 仅代理到堆的 peek() 以返回顶部元素。
• __is_empty__() 检查堆大小是否为 0 以查看栈是否为空。

总而言之，关键逻辑是 MinHeap 作为按插入时间排序的优先队列。将其作为底层数据存储，Stack 方法表现出 LIFO 行为，因为最新元素在堆中具有最高优先级。