std/src/collections/priority_queue.nv - main - nv-lang/nova

std/src/collections/priority_queue.nv
111 строк3 KB
Evgeniy Golovin
docs(endocs): перевод ///-комментариев collections на английский
01 авг 2026, 01:19
01 авг 2026, 01:196b13a19
// stdlib/priority_queue.nv — binary min-heap.
//
// API:
//   PriorityQueue[T Ord].new() -> PriorityQueue[T]
//   pq.push(item T)
//   pq.pop() -> Option[T]      // min element
//   pq.peek() -> Option[T]
//   pq.len -> int
//   pq.is_empty() -> bool

module collections.priority_queue

/// A priority queue (binary min-heap). Always pops the minimum element.
///
/// Requires `T: Ord` — the type must support the `<` operator.
/// `push` and `pop` run in O(log n).
///
/// # Examples
///
/// ```nova
/// let mut pq = PriorityQueue[int].new()
/// pq.push(5)
/// pq.push(1)
/// pq.push(3)
/// assert(pq.pop() == Some(1))
/// assert(pq.pop() == Some(3))
/// ```
#stable(since = "0.1")
export type PriorityQueue[T Ord] {
    mut items []T              // internal: heap-ordered, _items[0] = min
}

/// Create an empty `PriorityQueue`.
#stable(since = "0.1")
export fn PriorityQueue[T].new() -> Self =>
    { items: [] }

/// Number of elements in the queue.
#stable(since = "0.1")
export fn PriorityQueue[T] @len() -> int => @items.len()

/// Returns `true` if the queue is empty.
#stable(since = "0.1")
export fn PriorityQueue[T] @is_empty() -> bool => @items.len() == 0

/// Peek the minimum element without removing it.
#stable(since = "0.1")
export fn PriorityQueue[T] @peek() -> Option[T] {
    if @items.len() == 0 { None } else { Some(@items[0]) }
}

/// Add an element to the queue. O(log n).
#stable(since = "0.1")
export fn PriorityQueue[T] mut @push(item T) -> () {
    @items.push(item)
    @sift_up(@items.len() - 1)
}

/// Remove and return the minimum element. O(log n). `None` if empty.
#stable(since = "0.1")
export fn PriorityQueue[T] mut @pop() -> Option[T] {
    if @items.len() == 0 { return None }
    ro top = @items[0]
    ro last = @items.len() - 1
    // Переносим последний элемент в корень (swap — no-op при last == 0),
    // затем отбрасываем хвост через @pop() — bulk-copy rebuild не нужен.
    @items.swap(0, last)
    ro _ = @items.pop()
    if @items.len() > 0 {
        @sift_down(0)
    }
    Some(top)
}

// ──────────────────────────────────────────────────────────────────────────
// Heap operations
// ──────────────────────────────────────────────────────────────────────────

fn PriorityQueue[T] mut @sift_up(idx int) -> () {
    mut i = idx
    while i > 0 {
        ro parent = (i - 1) / 2
        if @items[i] < @items[parent] {
            @items.swap(i, parent)
            i = parent
        } else {
            return ()
        }
    }
}

fn PriorityQueue[T] mut @sift_down(idx int) -> () {
    mut i = idx
    ro n = @items.len()
    loop {
        ro left = 2 * i + 1
        ro right = 2 * i + 2
        mut smallest = i
        if left < n && @items[left] < @items[smallest] {
            smallest = left
        }
        if right < n && @items[right] < @items[smallest] {
            smallest = right
        }
        if smallest == i { return () }
        @items.swap(i, smallest)
        i = smallest
    }
}

// Тесты — см. peer-файл priority_queue_test.nv (module collections.priority_queue_test).