DEV Community
·
堆 - 最小堆与最大堆
💡
原文约1700字/词，阅读约需6分钟。
📝
内容提要
最小堆是一种高效的优先队列，结构为完整的二叉树，父节点的值总是小于或等于子节点。插入时，元素添加到末尾并通过上浮调整位置；删除时，根节点被移除，最后一个元素上升并通过下沉调整。最大堆则相反，父节点值大于或等于子节点。
🎯
关键要点
-
最小堆是一种高效的优先队列，结构为完整的二叉树。
-
父节点的值总是小于或等于子节点。
-
插入时，元素添加到末尾并通过上浮调整位置。
-
删除时，根节点被移除，最后一个元素上升并通过下沉调整。
-
最大堆则相反，父节点值大于或等于子节点。
-
堆的实现通常使用数组，元素的优先级在树的顶部。
-
完整的二叉树要求所有子节点的优先级小于或等于父节点。
-
插入操作需要比较新元素与父节点的值，必要时进行交换。
-
删除操作将根节点替换为最后一个元素，并通过下沉调整。
-
最小堆的下沉操作确保父节点的值小于或等于其子节点的值。
-
最大堆的下沉操作确保父节点的值大于或等于其子节点的值。
❓
延伸问答
什么是最小堆？
最小堆是一种高效的优先队列，结构为完整的二叉树，父节点的值总是小于或等于子节点。
最小堆的插入操作是如何进行的？
插入时，元素添加到末尾并通过上浮调整位置，确保父节点的值小于或等于子节点的值。
最小堆的删除操作是怎样的？
删除时，根节点被移除，最后一个元素上升并通过下沉调整，确保堆的性质保持不变。
最大堆与最小堆有什么区别？
最大堆的父节点值大于或等于子节点，而最小堆的父节点值小于或等于子节点。
如何实现堆的结构？
堆通常使用数组实现，元素的优先级在树的顶部，子节点和父节点的位置通过索引计算得出。
最小堆的下沉操作有什么作用？
下沉操作确保父节点的值小于或等于其子节点的值，以维持堆的性质。
➡️
