"PriorityQueue" (Data Structure)

"PriorityQueue"

represents a queue of elements where the highest-priority element is always returned.

Details

  • A priority queue has efficient insertion and removal operations:
  • CreateDataStructure["PriorityQueue"]create a new empty "PriorityQueue"
    Typed[x,"PriorityQueue"]give x the type "PriorityQueue"
  • For a data structure of type "PriorityQueue", the following operations can be used:
  • ds["DropAll"]drop all the elements from dstime: O(n)
    ds["EmptyQ"]return True if there are no elements stored in dstime: O(1)
    ds["Length"]return the number of elements stored in dstime: O(1)
    ds["Peek"]return the element with the highest priority from dstime: O(1)
    ds["Pop"]remove and return the element with the highest priority from dstime: O(log n)
    ds["Push",x]add x to the dstime: O(log n)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    FullForm[ds]full form of ds
    Information[ds]information about ds
    InputForm[ds]input form of ds
    Normal[ds]convert ds to a normal expression
  • The priority of two elements is determined by the Order function.
  • "PriorityQueue" is implemented with a heap data structure.

Examples

open allclose all

Basic Examples  (3)

A new "PriorityQueue" can be created with CreateDataStructure:

Initially there are no elements:

Insert three elements:

Remove and return the element with the highest priority:

Any data can be stored in a "PriorityQueue":

A visualization of the data structure shows that the heap property, where no node is smaller than its children, is maintained:

Any data can be stored in a "PriorityQueue":

Scope  (2)

Sorting  (1)

Random data:

Data inserted into and removed from a "PriorityQueue" will come out in reverse sorted order:

Information  (1)

A new "PriorityQueue" can be created with CreateDataStructure:

Information about the data structure ds:

Introduced in 2020
 (12.1)