"PriorityQueue" （数据结构）

"PriorityQueue"

表示一个元素队列，总是返回优先级最高的元素.

更多信息

  • 优先级队列可高效进行插入和删除操作：
  • CreateDataStructure["PriorityQueue"]创建新的空 "PriorityQueue"
    CreateDataStructure["PriorityQueue",elems]用元素元素 elems 创建一个新的 "PriorityQueue"
    CreateDataStructure["PriorityQueue",elems,p]用指定元素和排序函数 p 创建一个新的 "PriorityQueue"
    Typed[x,"PriorityQueue"]指定 x 的类型为 "PriorityQueue"
  • 对于类型为 "PriorityQueue" 的数据结构，可进行以下操作：
  • ds["Copy"]返回 ds 的副本时间：O(n)
    ds["DropAll"]删除 ds 中所有的元素时间：O(n)
    ds["Elements"]返回 ds 的元素列表时间：O(n)
    ds["EmptyQ"]如果 ds 中没有存储任何元素则返回 True时间：O(1)
    ds["Length"]返回 ds 中存储的元素的数量时间：O(1)
    ds["Peek"]返回 ds 中优先级最高的元素时间：O(1)
    ds["Pop"]删除并返回 ds 中优先级最高的元素时间：O(log n)
    ds["Push",x]将 x 添加到 ds 中时间：O(log n)
    ds["Visualization"]返回 ds 的可视化时间：O(n)
  • 还支持以下函数：
  • dsi===dsj如果 dsi 等于 dsj 则为 True
    FullForm[ds]ds 的完全形式
    Information[ds]关于 ds 的信息
    InputForm[ds]ds 的输入形式
    Normal[ds]将 ds 转换成普通表达式
  • 两个元素的顺序由排序函数 p 决定，跟在 Sort 的排序函数给出的释义之后. 默认的排序函数为 Order.
  • "PriorityQueue" 由堆数据结构实现.
  • 若初始元素规范为 Null，则会创建一个空的 "PriorityQueue".

范例

打开所有单元关闭所有单元

基本范例  (4)

可用 CreateDataStructure 创建新的 "PriorityQueue"：

开始时没有元素：

插入三个元素：

删除并返回优先级最高的元素：

可用 "PriorityQueue" 存储任意数据：

可视化数据结构显示了堆属性，即没有节点小于其子节点：

可用 "PriorityQueue" 存储任意数据：

函数可应用于元素对来决定它们的顺序：

规则列表：

推送并弹出该规则；并以第一个元素的顺序返回：

范围  (2)

排序  (1)

随机数据：

插入 "PriorityQueue" 的数据及从中删除的数据将以相反的顺序出现：

信息  (1)

可用 CreateDataStructure 创建新的 "PriorityQueue"：

关于数据结构 ds 的信息：

可能存在的问题  (1)

Sorting  (1)

优先队列数据结构通过堆（heap）实现. 这意味着元素并非保持完全排序的状态. 元素的顺序只保持了部分排序的堆属性.

这些插入可以得到一个有序元素组：

这些插入不会得到有序元素组：

提取元素会将其有序返回：

提取元素会将其有序返回：

若需要一个保持完全排序的缓冲区，则可能其他数据结构，如 "AVLTree"，会更合适.