"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"
    CreateDataStructure["PriorityQueue",elems]create a new "PriorityQueue" with elements elems
    CreateDataStructure["PriorityQueue",elems,p]create a new "PriorityQueue" with specified elements and ordering function p
    Typed[x,"PriorityQueue"]give x the type "PriorityQueue"
  • For a data structure of type "PriorityQueue", the following operations can be used:
  • ds["Copy"]return a copy of dstime: O(n)
    ds["DropAll"]drop all the elements from dstime: O(n)
    ds["Elements"]return a list of the elements of 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 order of two elements is determined by the order function p, following the interpretation given by the order function of Sort. The default order function is Order.
  • "PriorityQueue" is implemented with a heap data structure.
  • If the initial element specification is Null, an empty "PriorityQueue" is created.

Examples

open allclose all

Basic Examples  (4)

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":

A function can be applied to pairs of elements to determine their order:

A list of rules:

Push and then pop the rules; they are returned in order of the first elements:

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:

Possible Issues  (1)

Sorting  (1)

The priority queue data structure is implemented with a heap. This means that elements are not maintained in fully sorted order. The order of elements only maintains the heap property, which is partially sorted.

These insertions result in an ordered set of elements:

These insertions do not result in an ordered set of elements:

Extracting elements always returns them in order:

Extracting elements always returns them in order:

If a buffer that maintains fully sorted order is required, a different data structure, such as an "AVLTree", might be preferable.