堆与堆栈:是什么让它们与众不同?

作为程序员,您很可能遇到过“堆”和“堆栈”这两个术语。对于初学者来说,交替使用和错误地使用这两个术语是一种普遍的做法。

虽然数据结构课程的学生和有经验的程序员会很容易区分这两种数据结构,但在其他人看来它们是一样的。

程序员需要区分这两者,并在实际编程情况下适当地使用它们。面试官通常热衷于给申请人一个场景,然后要求最合适的数据结构。

继续阅读,我们将详细了解堆、堆栈、它们的差异和相关应用程序。

什么是堆?

程序员的堆通常是一种特殊的树数据结构,通常称为“优先级队列”。完全平衡二叉树结构的堆(回想一下,除了最后一层之外,完整二叉树的所有级别都被填充)并遵循堆属性,称为二叉堆。

堆属性以将最大值或最小值置于根部的方式构造树。

相关:学习如何免费编码的最佳方法

在 Max Heap 中,父节点的值大于子节点的值,并且树的根包含最大值。或者,Min Heap 被构造为以最小值为根,并且每个子节点的值都大于其父节点。对于二叉树中的每个节点,堆属性必须递归为真。

堆通常通过线性数组实现,数组的第一个元素( Arr[0] )代表根。对于特定节点i ,您可以在Arr[ (2*i) + 1 ]Arr[ (2*i) + 2]处检索子节点,类似地,父节点位于Arr[ (i-1) /2]索引。大多数语言(如 Java 和 C++)都包含为用户提供现成的最小和最大堆的库。

什么是堆栈?

堆栈是最早教给学生的数据结构之一,不应忽视它们。堆栈是一种数据结构,其行为类似于任何现实生活中的堆栈(卡片、盘子等)。堆栈只允许在一端进行操作,因此,它们具有 LIFO(后进先出)特性。相比之下,队列具有 FIFO(先进先出)特性并允许在两端进行操作。

典型的堆栈操作包括推送(将数据插入堆栈顶部)和弹出(删除最顶部的数据元素)。您可以根据需要通过指针、数组甚至链表来实现堆栈。 C++、C# 和 Java 都包含已经实现堆栈的库,因此您可以随时使用它们。

堆与堆栈

如果你读了这么多,你就会对栈和堆之间的区别有一个很好的了解。堆栈是线性的并具有 LIFO 特性,而堆具有树结构并遵循堆特性。它们都有不同的应用,我们将在下一节中讨论。

在渐近时间复杂度分析方面,您可以在 O(n) 中构建一个二元堆,并在 O(1) 中提取最小值或最大值。插入和删除可以在 O(log N) 时间内完成。相比之下,插入和删除在堆栈中花费 O(1) 时间。

典型应用

由于上面讨论的原因,当用作优先队列时,堆是非常有效的。诸如 Prim 的最小生成树和 Dijkstra 的最短路径之类的图算法通常使用堆作为优先级队列。堆的另一个重要应用是在 O(N logN) 时间内高效地对数组进行排序;这种排序技术被称为“堆排序”。

相关:插入排序算法简介

堆栈也有多种关键应用,例如内存管理和表达式求值。如果您遇到回溯编码问题,使用堆栈来节省时间可能是个好主意。

优先考虑数据结构

每个成功的程序员都会告诉你精通数据结构的重要性。在需要时尝试理解并习惯使用不同的数据结构是一个好主意,因为它是每个程序员的重要概念。