# "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 ds time: O(n) ds["DropAll"] drop all the elements from ds time: O(n) ds["Elements"] return a list of the elements of ds time: O(n) ds["EmptyQ"] return True if there are no elements stored in ds time: O(1) ds["Length"] return the number of elements stored in ds time: O(1) ds["Peek"] return the element with the highest priority from ds time: O(1) ds["Pop"] remove and return the element with the highest priority from ds time: O(log n) ds["Push",x] add x to the ds time: O(log n) ds["Visualization"] return a visualization of ds time: O(n)
• The following functions are also supported:
•  dsi===dsj True, 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.