BinaryHeap（最大/小堆）

Rust 常见内置 Traits 详解（一）：https://ipotato.me/article/59

BinaryHrap 源码解析：https://zhuanlan.zhihu.com/p/305107063

#[stable(feature = "rust1", since = "1.0.0")]
#[cfg_attr(not(test), rustc_diagnostic_item = "BinaryHeap")]
pub struct BinaryHeap<T> {
    data: Vec<T>, // T -> Ord
}
impl<T: Ord> BinaryHeap<T> {
    /// Creates an empty `BinaryHeap` as a max-heap.
    ///
    /// # Examples
    ///
    /// Basic usage:
    ///
    ///

/// use std::collections::BinaryHeap;
/// let mut heap = BinaryHeap::new();
/// heap.push(4);
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
#[must_use]
pub fn new() -> BinaryHeap<T> {
    BinaryHeap { data: vec![] }
}
/// Returns the length of the binary heap.
///
/// # Examples
///
/// Basic usage:
///
/// ```
/// use std::collections::BinaryHeap;
/// let heap = BinaryHeap::from([1, 3]);
///
/// assert_eq!(heap.len(), 2);
/// ```
#[must_use]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn len(&self) -> usize {
    self.data.len()
}
/// Pushes an item onto the binary heap.
///
/// # Examples
///
/// Basic usage:
///
/// ```
/// use std::collections::BinaryHeap;
/// let mut heap = BinaryHeap::new();
/// heap.push(3);
/// heap.push(5);
/// heap.push(1);
///
/// assert_eq!(heap.len(), 3);
/// assert_eq!(heap.peek(), Some(&5));
/// ```
///
/// # Time complexity
///
/// The expected cost of `push`, averaged over every possible ordering of
/// the elements being pushed, and over a sufficiently large number of
/// pushes, is *O*(1). This is the most meaningful cost metric when pushing
/// elements that are *not* already in any sorted pattern.
///
/// The time complexity degrades if elements are pushed in predominantly
/// ascending order. In the worst case, elements are pushed in ascending
/// sorted order and the amortized cost per push is *O*(log(*n*)) against a heap
/// containing *n* elements.
///
/// The worst case cost of a *single* call to `push` is *O*(*n*). The worst case
/// occurs when capacity is exhausted and needs a resize. The resize cost
/// has been amortized in the previous figures.
#[stable(feature = "rust1", since = "1.0.0")]
pub fn push(&mut self, item: T) {
    let old_len = self.len();
    self.data.push(item);
    // SAFETY: Since we pushed a new item it means that
    //  old_len = self.len() - 1 < self.len()
    unsafe { self.sift_up(0, old_len) };
}
// The implementations of sift_up and sift_down use unsafe blocks in
// order to move an element out of the vector (leaving behind a
// hole), shift along the others and move the removed element back into the
// vector at the final location of the hole.
// The `Hole` type is used to represent this, and make sure
// the hole is filled back at the end of its scope, even on panic.
// Using a hole reduces the constant factor compared to using swaps,
// which involves twice as many moves.
/// # Safety
///
/// The caller must guarantee that `pos < self.len()`.
unsafe fn sift_up(&mut self, start: usize, pos: usize) -> usize {
    // Take out the value at `pos` and create a hole.
    // SAFETY: The caller guarantees that pos < self.len()
    let mut hole = unsafe { Hole::new(&mut self.data, pos) };
    while hole.pos() > start {
        let parent = (hole.pos() - 1) / 2;
        // SAFETY: hole.pos() > start >= 0, which means hole.pos() > 0
        //  and so hole.pos() - 1 can't underflow.
        //  This guarantees that parent < hole.pos() so
        //  it's a valid index and also != hole.pos().
        // valid 正当的；有效的，有根据的
        // underflow 下溢
        // guarantee 保证
        if hole.element() <= unsafe { hole.get(parent) } {
            break;
        }
        // SAFETY: Same as above
        unsafe { hole.move_to(parent) };
    }
    hole.pos()
}

}

javascript 最小堆 （leetcode 丑数）链接：[https://leetcode.cn/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode-solution-uoqd/](https://leetcode.cn/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode-solution-uoqd/)
```javascript
var nthUglyNumber = function(n) {
    const factors = [2, 3, 5];
    const seen = new Set();
    const heap = new MinHeap();
    seen.add(1);
    heap.insert(1);
    let ugly = 0;
    for (let i = 0; i < n; i++) {
        ugly = heap.pop();
        for (const factor of factors) {
            const next = ugly * factor;
            if (!seen.has(next)) {
                seen.add(next);
                heap.insert(next);
            }
        }
    }
    return ugly;
};
// 最小堆
class MinHeap {
    constructor() {
        this.heap = [];
    }
    getParentIndex(i) {
        return (i - 1) >> 1;
    }
    getLeftIndex(i) {
        return i * 2 + 1;
    }
    getRightIndex(i) {
        return i * 2 + 2;
    }
    shiftUp(index) {
        if(index === 0) { return; }
        const parentIndex = this.getParentIndex(index);
        if(this.heap[parentIndex] > this.heap[index]){
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }  
    }
    swap(i1, i2) {
        const temp = this.heap[i1];
        this.heap[i1]= this.heap[i2];
        this.heap[i2] = temp;
    }
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
        return this.heap[0];
    }
    shiftDown(index) {
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if (this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] < this.heap[index]){
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }
    peek() {
        return this.heap[0];
    }
    size() {
        return this.heap.length;
    }
}