Skip to main content

Module sui::priority_queue

Priority queue implemented using a max heap.

use std::vector;

Struct PriorityQueue​

Struct representing a priority queue. The entries vector represents a max heap structure, where entries[0] is the root, entries[1] and entries[2] are the left child and right child of the root, etc. More generally, the children of entries[i] are at i * 2 + 1 and i * 2 + 2. The max heap should have the invariant that the parent node's priority is always higher than its child nodes' priorities.

public struct PriorityQueue<T: drop> has drop, store
Click to open
Fields
entries: vector<sui::priority_queue::Entry<T>>

Struct Entry​

public struct Entry<T: drop> has drop, store
Click to open
Fields
priority: u64
value: T

Constants​

For when heap is empty and there's no data to pop.

const EPopFromEmptyHeap: u64 = 0;

For when the value vector and priority vector have mismatched lengths

const ELengthMismatch: u64 = 1;

For when access a node of a priority_queue at an invalid index

const EIndexOutOfBounds: u64 = 2;

Function new​

Create a new priority queue from the input entry vectors.

public fun new<T: drop>(entries: vector<sui::priority_queue::Entry<T>>): sui::priority_queue::PriorityQueue<T>

Function pop_max​

Pop the entry with the highest priority value.

public fun pop_max<T: drop>(pq: &mut sui::priority_queue::PriorityQueue<T>): (u64, T)

Function insert​

Insert a new entry into the queue.

public fun insert<T: drop>(pq: &mut sui::priority_queue::PriorityQueue<T>, priority: u64, value: T)

Function new_entry​

public fun new_entry<T: drop>(priority: u64, value: T): sui::priority_queue::Entry<T>

Function create_entries​

public fun create_entries<T: drop>(p: vector<u64>, v: vector<T>): vector<sui::priority_queue::Entry<T>>

Function restore_heap_recursive​

fun restore_heap_recursive<T: drop>(v: &mut vector<sui::priority_queue::Entry<T>>, i: u64)

Function max_heapify_recursive​

Max heapify the subtree whose root is at index i. That means after this function finishes, the subtree should have the property that the parent node has higher priority than both child nodes.
This function assumes that all the other nodes in the subtree (nodes other than the root) do satisfy the max heap property.

fun max_heapify_recursive<T: drop>(v: &mut vector<sui::priority_queue::Entry<T>>, len: u64, i: u64)

Function priorities​

public fun priorities<T: drop>(pq: &sui::priority_queue::PriorityQueue<T>): vector<u64>