DEV Community
·
数据结构：堆
💡
原文约600字/词，阅读约需2分钟。
📝
内容提要
堆是一种线性列表，元素包含数据和优先级，通常以二叉树形式表示，根节点为最高优先级。主要操作有插入、删除和调整优先级，时间复杂度分别为O(log n)和O(n)。堆的构建可通过排序或优化方法，后者复杂度为O(n)。
🎯
关键要点
-
堆是一种线性列表，元素包含数据和优先级，通常以二叉树形式表示。
-
根节点为最高优先级，主要操作包括插入、删除和调整优先级。
-
插入、删除和调整优先级的时间复杂度为O(log n)，而堆的构建复杂度为O(n)。
-
堆的性质保证了根节点是优先级最高的元素。
-
插入操作通过将新元素添加到列表末尾并上升调整来完成。
-
删除操作总是移除优先级最高的元素，并用最后一个元素替代，然后进行下降调整。
-
堆的构建可以通过排序或优化方法，后者的复杂度为O(n)。
-
优化构建方法只需调整内部节点的优先级，复杂度为线性O(n)。
❓
延伸问答
堆是什么？
堆是一种线性列表，元素包含数据和优先级，通常以二叉树形式表示，根节点为最高优先级。
堆的主要操作有哪些？
堆的主要操作包括插入、删除和调整优先级。
插入和删除操作的时间复杂度是多少？
插入和删除操作的时间复杂度均为O(log n)。
如何构建一个堆？
堆的构建可以通过排序或优化方法，优化方法的复杂度为O(n)。
堆的根节点有什么特性？
堆的根节点是优先级最高的元素。
调整优先级的操作是如何进行的？
调整优先级的操作通过“上升”和“下降”来实现，分别对应于增加和减少优先级。
➡️
