Priority Queue¶

1

import "std/data/priority-queue";

PriorityQueue<T> struct¶

A priority queue in Spice is a commonly used data structure, in which every item has a priority attached to it. It is implemented as a binary max-heap stored in a contiguous array, so the item with the highest priority (the largest one according to the < operator) is always served first.

Time complexity:
Insert: O(log n)
Delete: O(log n)
Peek: O(1)

Priority queues pre-allocate space using an initial size and a resize factor to not have to re-allocate with every item pushed.

Constructors¶

ctor¶

1

public p PriorityQueue.ctor(unsigned long initAllocItems, const T& defaultValue)

Construct a priority queue pre-filled with a number of copies of a default value

Parameters

ctor¶

1

public p PriorityQueue.ctor(unsigned int initAllocItems)

Construct a priority queue, pre-allocating space for the given number of items

Parameters

ctor¶

1

public p PriorityQueue.ctor(unsigned long initAllocItems = INITIAL_CAPACITY)

Construct a priority queue, pre-allocating space for the given number of items

Parameters

ctor¶

1

public p PriorityQueue.ctor(const PriorityQueue<T>& original)

Construct a priority queue as a deep copy of another priority queue

Parameters

Methods¶

push¶

1

public p PriorityQueue.push(const T& item)

Add an item to the priority queue

Parameters

pop¶

1

public f<T> PriorityQueue.pop()

Retrieve the item with the highest priority and remove it from the priority queue

Returns: T — Item with the highest priority

peek¶

1

public f<T&> PriorityQueue.peek()

Retrieve the item with the highest priority without removing it from the priority queue

Returns: T& — Item with the highest priority

getSize¶

1

public f<long> PriorityQueue.getSize()

Retrieve the current size of the priority queue

Returns: long — Current size of the priority queue

getCapacity¶

1

public f<long> PriorityQueue.getCapacity()

Retrieve the current capacity of the priority queue

Returns: long — Current capacity of the priority queue

isEmpty¶

1

public f<bool> PriorityQueue.isEmpty()

Checks if the priority queue contains any items at the moment

Returns: bool — Empty or not empty

isFull¶

1

public f<bool> PriorityQueue.isFull()

Checks if the priority queue exhausts its capacity and needs to resize at the next call of push

Returns: bool — Full or not full

clear¶

1

public p PriorityQueue.clear()

Removes all items from the priority queue

reserve¶

1

public p PriorityQueue.reserve(unsigned long itemCount)

Reserves itemCount items

Parameters

pack¶

1

public p PriorityQueue.pack()

Frees allocated memory that is not used by the priority queue

Operators¶

operator=¶

1

public p operator=<T>(PriorityQueue<T>& this, const PriorityQueue<T>& newValue)

Copy-assign the contents of another priority queue into this one

Parameters

operator==¶

1

public f<bool> operator==<T>(const PriorityQueue<T>& lhs, const PriorityQueue<T>& rhs)

Check if two priority queues are equal, i.e. they hold the same items in the same priority order

Parameters

Returns: bool — Equal or not equal

operator!=¶

1

public f<bool> operator!=<T>(const PriorityQueue<T>& lhs, const PriorityQueue<T>& rhs)

Check if two priority queues are not equal

Parameters

Returns: bool — Not equal or equal