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>