优先级队列数据结构的术语？
Terminology for a priority queue data structure?
我一直在使用原始开发人员称为 heap 的数据结构，它用于实现优先级队列。
虽然有很多关于二叉树的文章，但 (min/max) 堆的定义似乎不太明确 （细节因实现而异）.
我注意到的一些特性不一定适用于二叉树结构。
- 同一个元素可以多次出现在队列中，而不会导致执行或实现复杂化。
- 搜索（虽然可能并且比穷举搜索更快），效率不高（因为每个节点的子元素不必平衡）。
- 由于搜索效率不高并且有可能出现重复，删除可能需要存储对
node 的引用，而不是使用 key 来查找节点（这是二叉树的常见做法）。
, compared to a binary tree where it's most common to delete+insert.
（与二叉树相比，最好的情况更好，最坏的情况更糟）
是否有更详细的数据结构术语来匹配这些特征？
或者它只是一个 min/max heap 恰好被用作 priority-queue？
注意，这里有一个 link 到一个 min-heap 具有上述特征。
我认为您混淆了二叉 搜索 树和二叉树。二叉树比其他任何东西都更像是一种形状——它是一棵树，其中每个节点最多有两个 children。节点不一定必须有值，如果有，也没有要求它们遵守任何特定规则。
二叉搜索树是一棵二叉树，每个节点都持有一个键，每个节点都遵守左子树中所有键都小于该节点键的规则，并且右子树中的所有键都大于节点的键。 （一些定义放宽了允许 less-than-or-equal-to 而不是小于等的要求）
还有许多其他数据结构是从不是 BST 的二叉树构建的。 k-d 树存储多维数据。二进制尝试存储位串。
所以我认为这里最好的描述是“二叉堆是完整的并服从堆属性的二叉树，它与二叉搜索树不同，尽管它们具有相同的底层形状（或多或少）。”
一个binary heap is a concrete implementation of the priority queue抽象数据结构。它很受欢迎，因为它易于实现、内存效率高且相当快：O(log n) 插入和 O(log n) 删除根（最小堆中的最小元素，最大堆中的最大元素）。大多数实现还提供一种 peek 方法，允许在不删除根元素的情况下查看它。
二叉堆在其他方面没有特别出色的表现。与您的观察相反，在二进制堆中查找特定项目需要顺序扫描。尽管节点是有序的（未排序），但该顺序不利于搜索。
二进制堆的典型实现是在数组中。由于形状属性（该结构可以看作是一个完美（或完全）的二叉树），这意味着父子关系是隐式表示的。这些项目按广度优先顺序存储在数组中。
正如用户 templatetypedef 在他的回答中指出的那样，二叉堆是一种特殊的二叉树，不应与二叉搜索树混淆，后者专门用于快速插入和删除项目，并且按键定位项目。
尽管更改堆中项目的优先级或从堆中删除任意项目非常容易，但您指出的问题是 定位 项目进行手术。在典型的二叉堆中，找到要修改的项目需要顺序搜索。如果您需要在堆中移动项目的能力，您通常会将二进制文件与字典或哈希映射结合起来，这些字典或哈希映射由项目的键索引。该值是数组中项目的索引。每次移动项目时都会更新该索引。这会以常数因子减慢堆操作，但使您能够在 O(1) 中定位项目。
还有一种叫做 Min-max heap 的东西，它是一种二进制堆，可以让您以 O(1) 的时间访问最小项和最大项。该实现与标准二进制最小堆的实现非常相似。
更令人困惑的是，还存在 d 元堆，即每个节点包含两个以上子节点的堆。例如，三元堆的每个节点有三个子节点。这些也是在带有隐式子指针的数组中实现的。
还有其他通常称为堆的数据结构，但实际上与堆根本没有关系，只是它们是优先级队列数据结构的不同实现。最流行的似乎是 Pairing heap、Fibonacci heap 和 Binomial heap，所有这些也可以用二叉树来实现。 （同样，不是二叉搜索树。）
几年前，我在我的博客中写了一篇关于二叉堆（和 d 元堆）的指导性介绍。如果您有兴趣，请查看 this entry，其中列出了该系列的所有文章。
我一直在使用原始开发人员称为 heap 的数据结构，它用于实现优先级队列。
虽然有很多关于二叉树的文章，但 (min/max) 堆的定义似乎不太明确 （细节因实现而异）.
我注意到的一些特性不一定适用于二叉树结构。
- 同一个元素可以多次出现在队列中，而不会导致执行或实现复杂化。
- 搜索（虽然可能并且比穷举搜索更快），效率不高（因为每个节点的子元素不必平衡）。
- 由于搜索效率不高并且有可能出现重复，删除可能需要存储对
node的引用，而不是使用key来查找节点（这是二叉树的常见做法）。
（与二叉树相比，最好的情况更好，最坏的情况更糟）
是否有更详细的数据结构术语来匹配这些特征？
或者它只是一个 min/max heap 恰好被用作 priority-queue？
注意，这里有一个 link 到一个 min-heap 具有上述特征。
我认为您混淆了二叉 搜索 树和二叉树。二叉树比其他任何东西都更像是一种形状——它是一棵树，其中每个节点最多有两个 children。节点不一定必须有值，如果有，也没有要求它们遵守任何特定规则。
二叉搜索树是一棵二叉树，每个节点都持有一个键，每个节点都遵守左子树中所有键都小于该节点键的规则，并且右子树中的所有键都大于节点的键。 （一些定义放宽了允许 less-than-or-equal-to 而不是小于等的要求）
还有许多其他数据结构是从不是 BST 的二叉树构建的。 k-d 树存储多维数据。二进制尝试存储位串。
所以我认为这里最好的描述是“二叉堆是完整的并服从堆属性的二叉树，它与二叉搜索树不同，尽管它们具有相同的底层形状（或多或少）。”
一个binary heap is a concrete implementation of the priority queue抽象数据结构。它很受欢迎，因为它易于实现、内存效率高且相当快：O(log n) 插入和 O(log n) 删除根（最小堆中的最小元素，最大堆中的最大元素）。大多数实现还提供一种 peek 方法，允许在不删除根元素的情况下查看它。
二叉堆在其他方面没有特别出色的表现。与您的观察相反，在二进制堆中查找特定项目需要顺序扫描。尽管节点是有序的（未排序），但该顺序不利于搜索。
二进制堆的典型实现是在数组中。由于形状属性（该结构可以看作是一个完美（或完全）的二叉树），这意味着父子关系是隐式表示的。这些项目按广度优先顺序存储在数组中。
正如用户 templatetypedef 在他的回答中指出的那样，二叉堆是一种特殊的二叉树，不应与二叉搜索树混淆，后者专门用于快速插入和删除项目，并且按键定位项目。
尽管更改堆中项目的优先级或从堆中删除任意项目非常容易，但您指出的问题是 定位 项目进行手术。在典型的二叉堆中，找到要修改的项目需要顺序搜索。如果您需要在堆中移动项目的能力，您通常会将二进制文件与字典或哈希映射结合起来，这些字典或哈希映射由项目的键索引。该值是数组中项目的索引。每次移动项目时都会更新该索引。这会以常数因子减慢堆操作，但使您能够在 O(1) 中定位项目。
还有一种叫做 Min-max heap 的东西，它是一种二进制堆，可以让您以 O(1) 的时间访问最小项和最大项。该实现与标准二进制最小堆的实现非常相似。
更令人困惑的是，还存在 d 元堆，即每个节点包含两个以上子节点的堆。例如，三元堆的每个节点有三个子节点。这些也是在带有隐式子指针的数组中实现的。
还有其他通常称为堆的数据结构，但实际上与堆根本没有关系，只是它们是优先级队列数据结构的不同实现。最流行的似乎是 Pairing heap、Fibonacci heap 和 Binomial heap，所有这些也可以用二叉树来实现。 （同样，不是二叉搜索树。）
几年前，我在我的博客中写了一篇关于二叉堆（和 d 元堆）的指导性介绍。如果您有兴趣，请查看 this entry，其中列出了该系列的所有文章。