优先队列

export function usePriorityQueue(
    compare = (a, b) => (a === b ? 0 : a > b ? 1 : -1),
) {
    const data = []
    function getLeftChildIndex(idx) {
        return (idx << 1) + 1
    }
    function getRightChildIndex(idx) {
        return (idx << 1) + 2
    }
    function getParentIndex(idx) {
        return (idx - 1) >> 1
    }
    function swap(x, y) {
        const t = data[x]
        data[x] = data[y]
        data[y] = t
    }
    function heapifyUp() {
        let curr = data.length - 1
        let p = getParentIndex(curr)
        while (curr > 0 && compare(data[curr], data[p]) <= 0) {
            swap(curr, p)
            curr = p
            p = getParentIndex(curr)
        }
    }
    function heapifyDown() {
        let curr = 0
        while (getLeftChildIndex(curr) < data.length) {
            let next = getLeftChildIndex(curr)
            if (
                getRightChildIndex(curr) < data.length &&
                compare(
                    data[getLeftChildIndex(curr)],
                    data[getRightChildIndex(curr)],
                ) > 0
            )
                next = getRightChildIndex(curr)
            if (compare(data[curr], data[next]) <= 0) break
            swap(curr, next)
            curr = next
        }
    }
    function push(e) {
        data.push(e)
        heapifyUp()
    }
    function pop() {
        if (data.length === 0) return null
        if (data.length === 1) return data.pop()
        const result = data[0]
        data[0] = data.pop()
        heapifyDown()
        return result
    }
    const peek = () => (data.length ? data[0] : null)
    const size = () => data.length
    const isEmpty = () => size() === 0
    return {
        push,
        pop,
        size,
        isEmpty,
        peek,
    }
}

pub struct PriorityQueue<T: Ord> {
    data: Vec<T>,
}

impl<T: Ord> PriorityQueue<T> {
    pub fn new() -> Self {
        Self { data: Vec::new() }
    }

    pub fn push(&mut self, value: T) {
        self.data.push(value);
        let mut i = self.data.len() - 1;
        while i > 0 {
            let parent = (i - 1) / 2;
            if self.data[i] <= self.data[parent] {
                self.data.swap(parent, i);
                i = parent;
            } else {
                break;
            }
        }
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.data.is_empty() {
            return None;
        }
        let result = self.data.swap_remove(0);
        let mut i = 0;
        while i * 2 + 1 < self.data.len() {
            let left = i * 2 + 1;
            let right = i * 2 + 2;
            let mut next = left;
            if right < self.data.len() && self.data[left] > self.data[right] {
                next = right;
            }
            if self.data[next] < self.data[i] {
                self.data.swap(next, i);
                i = next;
            } else {
                break;
            }
        }
        Some(result)
    }

    pub fn peek(&self) -> Option<&T> {
        self.data.first()
    }

    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    pub fn len(&self) -> usize {
        self.data.len()
    }

    pub fn clear(&mut self) {
        self.data.clear();
    }
}

package algo

func NewPriorityQueue[T any](compare func(a, b T) int) *PriorityQueue[T] {
    return &PriorityQueue[T]{compare, []T{}}
}

type PriorityQueue[T any] struct {
    compare func(a, b T) int
    data    []T
}

func (pq *PriorityQueue[T]) heapifyUp() {
    curr := len(pq.data) - 1
    for p := (curr - 1) / 2; curr > 0 && pq.compare(pq.data[curr], pq.data[p]) <= 0; p = (curr - 1) / 2 {
        pq.data[curr], pq.data[p] = pq.data[p], pq.data[curr]
        curr = p
    }
}

func (pq *PriorityQueue[T]) heapifyDown() {
    curr := 0
    for curr<<1+1 < len(pq.data) {
        child := curr<<1 + 1
        if child+1 < len(pq.data) && pq.compare(pq.data[child+1], pq.data[child]) < 0 {
            child++
        }
        if pq.compare(pq.data[child], pq.data[curr]) >= 0 {
            break
        }
        pq.data[curr], pq.data[child] = pq.data[child], pq.data[curr]
        curr = child
    }
}

func (pq *PriorityQueue[T]) Push(v T) {
    pq.data = append(pq.data, v)
    pq.heapifyUp()
}

func (pq *PriorityQueue[T]) Pop() (T, bool) {
    var res T
    if pq.Len() == 0 {
        return res, false
    }
    res = pq.data[0]
    pq.data[0] = pq.data[len(pq.data)-1]
    pq.data = pq.data[:len(pq.data)-1]
    pq.heapifyDown()
    return res, true
}

func (pq *PriorityQueue[T]) Peek() (T, bool) {
    var value T
    if pq.Len() == 0 {
        return value, false
    }
    return pq.data[0], true
}

func (pq *PriorityQueue[T]) Len() int {
    return len(pq.data)
}

func (pq *PriorityQueue[T]) IsEmpty() bool {
    return pq.Len() == 0
}