Skip to main content

Module 0x2::priority_queue

Priority queue implemented using a max heap.

use 0x1::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 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.

struct PriorityQueue<T: drop> has drop, store

Struct Entry

struct Entry<T: drop> has drop, store
priority: u64
value: T


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

const EPopFromEmptyHeap: u64 = 0;

Function new

Create a new priority queue from the input entry vectors.

public fun new<T: drop>(entries: vector<priority_queue::Entry<T>>): priority_queue::PriorityQueue<T>
public fun new<T: drop>(mut entries: vector<Entry<T>>) : PriorityQueue<T> {
    let len = entries.length();
    let mut i = len / 2;
    // Max heapify from the first node that is a parent (node at len / 2).
    while (i > 0) {
        i = i - 1;
        max_heapify_recursive(&mut entries, len, i);
    PriorityQueue { entries }

Function pop_max

Pop the entry with the highest priority value.

public fun pop_max<T: drop>(pq: &mut priority_queue::PriorityQueue<T>): (u64, T)
public fun pop_max<T: drop>(pq: &mut PriorityQueue<T>) : (u64, T) {
    let len = pq.entries.length();
    assert!(len > 0, EPopFromEmptyHeap);
    // Swap the max element with the last element in the entries and remove the max element.
    let Entry { priority, value } = pq.entries.swap_remove(0);
    // Now the max heap property has been violated at the root node, but nowhere else
    // so we call max heapify on the root node.
    max_heapify_recursive(&mut pq.entries, len - 1, 0);
    (priority, value)

Function insert

Insert a new entry into the queue.

public fun insert<T: drop>(pq: &mut priority_queue::PriorityQueue<T>, priority: u64, value: T)
public fun insert<T: drop>(pq: &mut PriorityQueue<T>, priority: u64, value: T) {
    pq.entries.push_back(Entry { priority, value});
    let index = pq.entries.length() - 1;
    restore_heap_recursive(&mut pq.entries, index);

Function new_entry

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

Function create_entries

public fun create_entries<T: drop>(p: vector<u64>, v: vector<T>): vector<priority_queue::Entry<T>>
public fun create_entries<T: drop>(mut p: vector<u64>, mut v: vector<T>): vector<Entry<T>> {
    let len = p.length();
    assert!(v.length() == len, 0);
    let mut res = vector[];
    let mut i = 0;
    while (i < len) {
        let priority = p.remove(0);
        let value = v.remove(0);
        res.push_back(Entry { priority, value });
        i = i + 1;

Function restore_heap_recursive

fun restore_heap_recursive<T: drop>(v: &mut vector<priority_queue::Entry<T>>, i: u64)
fun restore_heap_recursive<T: drop>(v: &mut vector<Entry<T>>, i: u64) {
    if (i == 0) {
    let parent = (i - 1) / 2;

    // If new elem is greater than its parent, swap them and recursively
    // do the restoration upwards.
    if (*&v[i].priority > *&v[parent].priority) {
        v.swap(i, parent);
        restore_heap_recursive(v, parent);

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<priority_queue::Entry<T>>, len: u64, i: u64)
fun max_heapify_recursive<T: drop>(v: &mut vector<Entry<T>>, len: u64, i: u64) {
    if (len == 0) {
    assert!(i < len, 1);
    let left = i * 2 + 1;
    let right = left + 1;
    let mut max = i;
    // Find the node with highest priority among node `i` and its two children.
    if (left < len && *&v[left].priority > *&v[max].priority) {
        max = left;
    if (right < len && *&v[right].priority > *&v[max].priority) {
        max = right;
    // If the parent node (node `i`) doesn't have the highest priority, we swap the parent with the
    // max priority node.
    if (max != i) {
        v.swap(max, i);
        // After the swap, we have restored the property at node `i` but now the max heap property
        // may be violated at node `max` since this node now has a new value. So we need to now
        // max heapify the subtree rooted at node `max`.
        max_heapify_recursive(v, len, max);

Function priorities

public fun priorities<T: drop>(pq: &priority_queue::PriorityQueue<T>): vector<u64>
public fun priorities<T: drop>(pq: &PriorityQueue<T>): vector<u64> {
    let mut res = vector[];
    let mut i = 0;
    while (i < pq.entries.length()) {
        i = i +1;