//! 用二进制堆实现的优先级队列。
//!
//! 插入和弹出最大元素具有 *O*(log(*n*)) 时间复杂度。
//! 检查最大的元素是 *O*(1)。可以就地将 vector 转换为二进制堆，并且复杂度为 *O*(*n*)。
//! 二元堆也可以就地转换为已排序的 vector，允许它用于 *O*(*n* * log(*n*)) 就地堆排序。
//!
//! # Examples
//!
//! 这是一个较大的示例，实现了 [Dijkstra 算法][dijkstra] 来解决 [有向图][dir_graph] 上的 [最短路径问题][sssp]。
//!
//! 它显示了如何将 [`BinaryHeap`] 与自定义类型一起使用。
//!
//! [dijkstra]: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
//! [sssp]: https://en.wikipedia.org/wiki/Shortest_path_problem
//! [dir_graph]: https://en.wikipedia.org/wiki/Directed_graph
//!
//! ```
//! use std::cmp::Ordering;
//! use std::collections::BinaryHeap;
//!
//! #[derive(Copy, Clone, Eq, PartialEq)]
//! struct State {
//!     cost: usize,
//!     position: usize,
//! }
//!
//! // 优先级队列取决于 `Ord`。
//! // 显式实现 trait，以便队列成为最小堆而不是最大堆。
//! //
//! impl Ord for State {
//!     fn cmp(&self, other: &Self) -> Ordering {
//!         // 请注意，我们翻转了费用排序。
//!         // 在平局的情况下，我们比较位置 - 必须执行此步骤才能使 `PartialEq` 和 `Ord` 的实现保持一致。
//!         //
//!         other.cost.cmp(&self.cost)
//!             .then_with(|| self.position.cmp(&other.position))
//!     }
//! }
//!
//! // `PartialOrd` 也需要实现。
//! impl PartialOrd for State {
//!     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
//!         Some(self.cmp(other))
//!     }
//! }
//!
//! // 对于较短的实现，每个节点都表示为 `usize`。
//! struct Edge {
//!     node: usize,
//!     cost: usize,
//! }
//!
//! // Dijkstra 的最短路径算法。
//!
//! // 从 `start` 开始，并使用 `dist` 跟踪到每个节点的当前最短距离。此实现的内存效率不高，因为它可能会将重复的节点留在队列中。
//! //
//! // 它还将 `usize::MAX` 用作标记值，以实现更简单的实现。
//! //
//! fn shortest_path(adj_list: &Vec<Vec<Edge>>, start: usize, goal: usize) -> Option<usize> {
//!     // dist[node] = 当前从 `start` 到 `node` 的最短距离
//!     let mut dist: Vec<_> = (0..adj_list.len()).map(|_| usize::MAX).collect();
//!
//!     let mut heap = BinaryHeap::new();
//!
//!     // 我们正处于 `start` 阶段，成本为零
//!     dist[start] = 0;
//!     heap.push(State { cost: 0, position: start });
//!
//!     // 首先检查成本较低的节点的边界 (min-heap)
//!     while let Some(State { cost, position }) = heap.pop() {
//!         // 或者，我们可以继续找到所有最短的路径
//!         if position == goal { return Some(cost); }
//!
//!         // 重要，因为我们可能已经找到了更好的方法
//!         if cost > dist[position] { continue; }
//!
//!         // 对于我们可以到达的每个节点，看看是否可以找到一种成本更低的方法通过该节点
//!         //
//!         for edge in &adj_list[position] {
//!             let next = State { cost: cost + edge.cost, position: edge.node };
//!
//!             // 如果是这样，请将其添加到边界并继续
//!             if next.cost < dist[next.position] {
//!                 heap.push(next);
//!                 // 放松，我们现在找到了更好的方法
//!                 dist[next.position] = next.cost;
//!             }
//!         }
//!     }
//!
//!     // 无法达成目标
//!     None
//! }
//!
//! fn main() {
//!     // 这是我们将要使用的有向图。
//!     // 节点编号对应于不同的状态，并且 edge 权重表示从一个节点移动到另一个节点的成本。
//!     //
//!     // 请注意，edges 是单向的。
//!     //
//!     //                  7
//!     //          +-----------------+
//!     //          |                 |
//!     //          v   1        2    |  2
//!     //          0 -----> 1 -----> 3 ---> 4
//!     //          |        ^        ^      ^
//!     //          |        | 1      |      |
//!     //          |        |        | 3    | 1 +------> 2 -------+      |
//!     //           10      |               |
//!     //                   +---------------+
//!     //
//!     // 该图表示为邻接表，其中每个索引 (对应于节点值) 具有传出 edges 的列表。
//!     // 选择它的效率。
//!     //
//!     //
//!     //
//!     let graph = vec![
//!         // 节点 0
//!         vec![Edge { node: 2, cost: 10 },
//!              Edge { node: 1, cost: 1 }],
//!         // 节点 1
//!         vec![Edge { node: 3, cost: 2 }],
//!         // 节点 2
//!         vec![Edge { node: 1, cost: 1 },
//!              Edge { node: 3, cost: 3 },
//!              Edge { node: 4, cost: 1 }],
//!         // 节点 3
//!         vec![Edge { node: 0, cost: 7 },
//!              Edge { node: 4, cost: 2 }],
//!         // 节点 4
//!         vec![]];
//!
//!     assert_eq!(shortest_path(&graph, 0, 1), Some(1));
//!     assert_eq!(shortest_path(&graph, 0, 3), Some(3));
//!     assert_eq!(shortest_path(&graph, 3, 0), Some(7));
//!     assert_eq!(shortest_path(&graph, 0, 4), Some(5));
//!     assert_eq!(shortest_path(&graph, 4, 0), None);
//! }
//! ```
//!
//!

#![allow(missing_docs)]
#![stable(feature = "rust1", since = "1.0.0")]

use core::fmt;
use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedLen};
use core::mem::{self, swap, ManuallyDrop};
use core::num::NonZeroUsize;
use core::ops::{Deref, DerefMut};
use core::ptr;

use crate::collections::TryReserveError;
use crate::slice;
use crate::vec::{self, AsVecIntoIter, Vec};

#[cfg(test)]
mod tests;

/// 用二进制堆实现的优先级队列。
///
/// 这将是一个最大的堆。
///
/// 项的修改方式是一个逻辑错误，即项相对于任何其他项的排序 (由 [`Ord`] trait 确定) 在它在堆中时发生变化。这通常只能通过内部可变性、全局状态、I/O 或不安全代码实现。由这种逻辑错误导致的行为没有被指定，但会封装到观察到逻辑错误的 `BinaryHeap` 中，并且不会导致未定义的行为。
///
/// 这可能包括 panics、不正确的结果、中止、内存泄漏和未中止。
///
/// 只要元素在堆中时如上所述没有改变它们的相对顺序，`BinaryHeap` 的 API 就保证堆不，变体，保持不变，即它的方法都按照文档的方式运行。
/// 例如，如果一个方法被记录为按排序顺序迭代，那么只要堆中的元素没有改变顺序，它就可以保证工作，即使存在闭包被展开、迭代器被泄漏以及类似的愚蠢行为。
///
/// # Examples
///
/// ```
/// use std::collections::BinaryHeap;
///
/// // 通过类型推断，我们可以省略显式类型签名 (在本示例中为 `BinaryHeap<i32>`)。
/////
/// let mut heap = BinaryHeap::new();
///
/// // 我们可以使用 peek 来查看堆中的下一个项。
/// // 在这种情况下，那里还没有项目，所以我们得到 None。
/// assert_eq!(heap.peek(), None);
///
/// // 让我们添加一些分数...
/// heap.push(1);
/// heap.push(5);
/// heap.push(2);
///
/// // 现在，窥视显示了堆中最重要的项。
/// assert_eq!(heap.peek(), Some(&5));
///
/// // 我们可以检查堆的长度。
/// assert_eq!(heap.len(), 3);
///
/// // 我们可以遍历堆中的项，尽管它们是按随机顺序返回的。
/////
/// for x in &heap {
///     println!("{x}");
/// }
///
/// // 如果我们改为弹出这些分数，它们应该按顺序返回。
/// assert_eq!(heap.pop(), Some(5));
/// assert_eq!(heap.pop(), Some(2));
/// assert_eq!(heap.pop(), Some(1));
/// assert_eq!(heap.pop(), None);
///
/// // 我们可以清除任何剩余项的堆。
/// heap.clear();
///
/// // 堆现在应该为空。
/// assert!(heap.is_empty())
/// ```
///
/// 可以从数组初始化具有已知项列表的 `BinaryHeap`：
///
/// ```
/// use std::collections::BinaryHeap;
///
/// let heap = BinaryHeap::from([1, 5, 2]);
/// ```
///
/// ## Min-heap
///
/// [`core::cmp::Reverse`] 或自定义 [`Ord`] 实现可用于使 `BinaryHeap` 成为最小堆。这使 `heap.pop()` 返回最小值而不是最大值。
///
/// ```
/// use std::collections::BinaryHeap;
/// use std::cmp::Reverse;
///
/// let mut heap = BinaryHeap::new();
///
/// // 在 `Reverse` 中包装值
/// heap.push(Reverse(1));
/// heap.push(Reverse(5));
/// heap.push(Reverse(2));
///
/// // 如果我们现在弹出这些分数，它们应该以相反的顺序返回。
/// assert_eq!(heap.pop(), Some(Reverse(1)));
/// assert_eq!(heap.pop(), Some(Reverse(2)));
/// assert_eq!(heap.pop(), Some(Reverse(5)));
/// assert_eq!(heap.pop(), None);
/// ```
///
/// # 时间复杂度
///
/// | [push]  | [pop]         | [peek]/[peek\_mut] |
/// |---------|---------------|--------------------|
/// | *O*(1)~ | *O*(log(*n*)) | *O*(1)             |
///
/// `push` 的值是预期成本； 方法文档提供了更详细的分析。
///
/// [`core::cmp::Reverse`]: core::cmp::Reverse
/// [`Cell`]: core::cell::Cell
/// [`RefCell`]: core::cell::RefCell
/// [push]: BinaryHeap::push
/// [pop]: BinaryHeap::pop
/// [peek]: BinaryHeap::peek
/// [peek\_mut]: BinaryHeap::peek_mut
///
///
///
///
///
///
///
///
///
///
///
///
///
#[stable(feature = "rust1", since = "1.0.0")]
#[cfg_attr(not(test), rustc_diagnostic_item = "BinaryHeap")]
pub struct BinaryHeap<T> {
    data: Vec<T>,
}

/// 将可变引用引至 `BinaryHeap` 上最大部分的结构体。
///
///
/// 该 `struct` 是通过 [`BinaryHeap`] 上的 [`peek_mut`] 方法创建的。
/// 有关更多信息，请参见其文档。
///
/// [`peek_mut`]: BinaryHeap::peek_mut
#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
pub struct PeekMut<'a, T: 'a + Ord> {
    heap: &'a mut BinaryHeap<T>,
    // 如果需要 set_len + sift_down，这是 Some。
    // 如果 &mut T 尚未暴露给 peek_mut () 的调用者，则为 None。
    original_len: Option<NonZeroUsize>,
}

#[stable(feature = "collection_debug", since = "1.17.0")]
impl<T: Ord + fmt::Debug> fmt::Debug for PeekMut<'_, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("PeekMut").field(&self.heap.data[0]).finish()
    }
}

#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
impl<T: Ord> Drop for PeekMut<'_, T> {
    fn drop(&mut self) {
        if let Some(original_len) = self.original_len {
            // SAFETY: 这是 PeekMut::deref_mut 调用时 Vec 中的元素数量，因此也是 BinaryHeap::peek_mut 调用时的元素数量。
            // 由于 PeekMut 最终没有泄漏，我们现在正在取消 DerefMut 准备好的泄漏放大。
            //
            //
            //
            unsafe { self.heap.data.set_len(original_len.get()) };

            // SAFETY: PeekMut 仅针对非空堆实例化。
            unsafe { self.heap.sift_down(0) };
        }
    }
}

#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
impl<T: Ord> Deref for PeekMut<'_, T> {
    type Target = T;
    fn deref(&self) -> &T {
        debug_assert!(!self.heap.is_empty());
        // SAFE: 仅针对非空堆实例化 PeekMut
        unsafe { self.heap.data.get_unchecked(0) }
    }
}

#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
impl<T: Ord> DerefMut for PeekMut<'_, T> {
    fn deref_mut(&mut self) -> &mut T {
        debug_assert!(!self.heap.is_empty());

        let len = self.heap.len();
        if len > 1 {
            // 在这里，我们先发制人地在当前最大元素之后泄漏所有剩余的底层 vector。
            // 如果调用者改变了我们将要提供给他们的 &mut T，然后泄露了 PeekMut，那么所有这些元素都将保持泄露状态。
            //
            // 如果他们不泄漏 PeekMut，那么丢弃或 PeekMut::pop 将不泄漏 vector 元素。
            //
            // 这种技术在标准库的其他几个地方被描述为 "leak amplification"。
            //
            //
            unsafe {
                // SAFETY: len > 1 so len !=  0.
                self.original_len = Some(NonZeroUsize::new_unchecked(len));
                // SAFETY: len > 1 所以现在所做的只是泄漏元素，这是安全的。
                //
                self.heap.data.set_len(1);
            }
        }

        // SAFE: 仅针对非空堆实例化 PeekMut
        unsafe { self.heap.data.get_unchecked_mut(0) }
    }
}

impl<'a, T: Ord> PeekMut<'a, T> {
    /// 从堆中删除偷看的值并返回它。
    #[stable(feature = "binary_heap_peek_mut_pop", since = "1.18.0")]
    pub fn pop(mut this: PeekMut<'a, T>) -> T {
        if let Some(original_len) = this.original_len.take() {
            // SAFETY: 这是 BinaryHeap::peek_mut 调用时 Vec 中的元素数量。
            //
            unsafe { this.heap.data.set_len(original_len.get()) };

            // 与抛弃不同，这里我们也不需要做 sift_down，即使调用者可能已经改变了元素。
            // 它在下一行从堆中移除并且 pop() 对其值不敏感。
            //
        }
        this.heap.pop().unwrap()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Clone> Clone for BinaryHeap<T> {
    fn clone(&self) -> Self {
        BinaryHeap { data: self.data.clone() }
    }

    fn clone_from(&mut self, source: &Self) {
        self.data.clone_from(&source.data);
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Ord> Default for BinaryHeap<T> {
    /// 创建一个空的 `BinaryHeap<T>`。
    #[inline]
    fn default() -> BinaryHeap<T> {
        BinaryHeap::new()
    }
}

#[stable(feature = "binaryheap_debug", since = "1.4.0")]
impl<T: fmt::Debug> fmt::Debug for BinaryHeap<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self.iter()).finish()
    }
}

struct RebuildOnDrop<'a, T: Ord> {
    heap: &'a mut BinaryHeap<T>,
    rebuild_from: usize,
}

impl<'a, T: Ord> Drop for RebuildOnDrop<'a, T> {
    fn drop(&mut self) {
        self.heap.rebuild_tail(self.rebuild_from);
    }
}

impl<T: Ord> BinaryHeap<T> {
    /// 创建一个空的 `BinaryHeap` 作为最大堆。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// 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![] }
    }

    /// 创建一个至少具有指定容量的空 `BinaryHeap`。
    ///
    /// 二进制堆将能够保存至少 `capacity` 个元素而无需重新分配。
    /// 此方法允许分配比 `capacity` 更多的元素。
    /// 如果 `capacity` 为 0，则不会分配二进制堆。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap = BinaryHeap::with_capacity(10);
    /// heap.push(4);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    #[must_use]
    pub fn with_capacity(capacity: usize) -> BinaryHeap<T> {
        BinaryHeap { data: Vec::with_capacity(capacity) }
    }

    /// 返回二进制堆中最大项的变量引用; 如果为空，则返回 `None`。
    ///
    /// Note: 如果 `PeekMut` 值泄漏，一些堆元素可能会随之泄漏，但其余元素将保持有效堆。
    ///
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap = BinaryHeap::new();
    /// assert!(heap.peek_mut().is_none());
    ///
    /// heap.push(1);
    /// heap.push(5);
    /// heap.push(2);
    /// {
    ///     let mut val = heap.peek_mut().unwrap();
    ///     *val = 0;
    /// }
    /// assert_eq!(heap.peek(), Some(&2));
    /// ```
    ///
    /// # 时间复杂度
    ///
    /// 如果该项被修改，则最坏情况下的时间复杂度为 *O*(log(*n*))，否则为 *O*(1)。
    ///
    ///
    ///
    #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
    pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>> {
        if self.is_empty() { None } else { Some(PeekMut { heap: self, original_len: None }) }
    }

    /// 从二进制堆中删除最大的项并返回它; 如果为空，则返回 `None`。
    ///
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap = BinaryHeap::from([1, 3]);
    ///
    /// assert_eq!(heap.pop(), Some(3));
    /// assert_eq!(heap.pop(), Some(1));
    /// assert_eq!(heap.pop(), None);
    /// ```
    ///
    /// # 时间复杂度
    ///
    /// `pop` 在包含 *n* 个元素的堆上的最坏情况代价是 *O*(log(*n*))。
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn pop(&mut self) -> Option<T> {
        self.data.pop().map(|mut item| {
            if !self.is_empty() {
                swap(&mut item, &mut self.data[0]);
                // SAFETY: `!self.is_empty()` 表示 `self.len() > 0`
                unsafe { self.sift_down_to_bottom(0) };
            }
            item
        })
    }

    /// 将项目推入二进制堆。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// 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));
    /// ```
    ///
    /// # 时间复杂度
    ///
    /// `push` 的预期成本是 *O*(1)，该成本是在被推元素的每个可能排序以及足够大量的推数上平均的。
    ///
    /// 当推送尚未处于任何排序模式的元素时，这是最有意义的成本指标。
    ///
    /// 如果元素主要以升序推入，则时间复杂度会降低。
    /// 在最坏的情况下，元素以升序排序，并且每次推送的摊销成本为 *O*(log(*n*)) 对包含 *n* 个元素的堆。
    ///
    /// 对 `push` 进行 `*` 调用的最坏情况是 *O*(*n*)。最坏的情况发生在容量用尽并需要调整大小时。
    /// 调整大小成本已在之前的数字中摊销。
    ///
    ///
    ///
    ///
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn push(&mut self, item: T) {
        let old_len = self.len();
        self.data.push(item);
        // SAFETY: 由于我们推送了一个新项，这意味着 old_len= self.len()-1 <self.len()
        //
        unsafe { self.sift_up(0, old_len) };
    }

    /// 消耗 `BinaryHeap` 并按已排序的 (ascending) 顺序返回 vector。
    ///
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    ///
    /// let mut heap = BinaryHeap::from([1, 2, 4, 5, 7]);
    /// heap.push(6);
    /// heap.push(3);
    ///
    /// let vec = heap.into_sorted_vec();
    /// assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]);
    /// ```
    #[must_use = "`self` will be dropped if the result is not used"]
    #[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
    pub fn into_sorted_vec(mut self) -> Vec<T> {
        let mut end = self.len();
        while end > 1 {
            end -= 1;
            // SAFETY: `end` 从 `self.len() - 1` 变为 1 (均包括在内)，因此它始终是可访问的有效索引。
            //
            //  访问索引 0 (即 `ptr`) 是安全的，因为
            //  1 <= end < self.len(), which means self.len() >=  2.
            unsafe {
                let ptr = self.data.as_mut_ptr();
                ptr::swap(ptr, ptr.add(end));
            }
            // SAFETY: `end` 从 `self.len() - 1` 变为 1 (均包括在内)，因此：
            //  `0 < 1 <= end <= self.len() - 1 < self.len()`，这意味着 `0 < end` 并且 `end < self.len()`。
            //
            unsafe { self.sift_down_range(0, end) };
        }
        self.into_vec()
    }

    // sift_up 和 sift_down 的实现使用不安全的块，以将元素从 vector 中移出 (留在 hole 后面)，沿其他元素移动，然后将移除的元素在 hole 的最终位置移回 vector 中。
    //
    // `Hole` 类型用于表示这一点，并确保 hole 在其作用域的末尾 (即使在 panic 上) 也被填充回去。
    // 与使用掉期相比，使用 hole 减少了常量因子，掉期涉及两倍的移动次数。
    //
    //
    //
    //

    /// # Safety
    ///
    /// 调用者必须保证 `pos < self.len()`。
    unsafe fn sift_up(&mut self, start: usize, pos: usize) -> usize {
        // 取出 `pos` 处的值，并创建一个 hole。
        // SAFETY: 调用者保证 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，这意味着 hole.pos() > 0，因此  hole.pos() - 1 不能下溢。
            //
            //  这样可以保证 `parent < hole.pos()`，因此它是一个有效的索引，而且 `!= hole.pos()`。
            //
            if hole.element() <= unsafe { hole.get(parent) } {
                break;
            }

            // SAFETY: 同上
            unsafe { hole.move_to(parent) };
        }

        hole.pos()
    }

    /// 在 `pos` 处取一个元素，然后将其向下移动到堆中，而其子元素较大。
    ///
    ///
    /// # Safety
    ///
    /// 调用者必须保证 `pos < end <= self.len()`。
    unsafe fn sift_down_range(&mut self, pos: usize, end: usize) {
        // SAFETY: 调用者保证 pos <end <= self.len()。
        let mut hole = unsafe { Hole::new(&mut self.data, pos) };
        let mut child = 2 * hole.pos() + 1;

        // Loop invariant: child == 2 * hole.pos() +  1.
        while child <= end.saturating_sub(2) {
            // 比较两个子节点中较大的一个
            // SAFETY: child <end-1 <self.len() 和 child + 1 <end <= self.len()，因此它们是有效索引。
            //
            //  `child == 2 * hole.pos() + 1 != hole.pos()` 和 `child + 1 == 2 * hole.pos() + 2 != hole.pos().`。
            // FIXME: 如果 T 是 ZST，则 `2 * hole.pos() + 1` 或 `2 * hole.pos() + 2` 可能溢出
            //
            //
            child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize;

            // 如果我们已经整齐了，那就停下来。
            // SAFETY: child 要么是老节点要么是老节点 + 1，我们已经证明它们都是 `< self.len()` 和 `!= hole.pos()`
            //
            if hole.element() >= unsafe { hole.get(child) } {
                return;
            }

            // SAFETY: 与上述相同。
            unsafe { hole.move_to(child) };
            child = 2 * hole.pos() + 1;
        }

        // SAFETY: && 短路，这意味着在第二种情况下 `child == end - 1 < self.len()` 已经是正确的。
        //
        if child == end - 1 && hole.element() < unsafe { hole.get(child) } {
            // SAFETY: child 已被证明是有效的索引，`child == 2 * hole.pos() + 1 != hole.pos()`。
            //
            unsafe { hole.move_to(child) };
        }
    }

    /// # Safety
    ///
    /// 调用者必须保证 `pos < self.len()`。
    unsafe fn sift_down(&mut self, pos: usize) {
        let len = self.len();
        // SAFETY: `pos < len` 是由调用者保证的，并且显然 `len = self.len() <= self.len()`。
        //
        unsafe { self.sift_down_range(pos, len) };
    }

    /// 在 `pos` 处获取一个元素，并将其一直向下移动到堆中，然后将其筛选到其位置。
    ///
    ///
    /// Note: 当已知元素很大 / 应该更靠近底部时，这就更快了。
    ///
    /// # Safety
    ///
    /// 调用者必须保证 `pos < self.len()`。
    ///
    unsafe fn sift_down_to_bottom(&mut self, mut pos: usize) {
        let end = self.len();
        let start = pos;

        // SAFETY: 调用者保证 `pos < self.len()`。
        let mut hole = unsafe { Hole::new(&mut self.data, pos) };
        let mut child = 2 * hole.pos() + 1;

        // Loop invariant: child == 2 * hole.pos() +  1.
        while child <= end.saturating_sub(2) {
            // SAFETY: child <end-1 <self.len() 和 child + 1 <end <= self.len()，因此它们是有效索引。
            //
            //  `child == 2 * hole.pos() + 1 != hole.pos()` 和 `child + 1 == 2 * hole.pos() + 2 != hole.pos().`。
            // FIXME: 如果 T 是 ZST，则 `2 * hole.pos() + 1` 或 `2 * hole.pos() + 2` 可能溢出
            //
            //
            child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize;

            // SAFETY: 同上
            unsafe { hole.move_to(child) };
            child = 2 * hole.pos() + 1;
        }

        if child == end - 1 {
            // SAFETY: `child == end - 1 < self.len()`，所以它是一个有效的索引，`child == 2 * hole.pos() + 1 != hole.pos()`。
            //
            unsafe { hole.move_to(child) };
        }
        pos = hole.pos();
        drop(hole);

        // SAFETY: pos 是 hole 中的位置，并且已经被证明是有效的索引。
        //
        unsafe { self.sift_up(start, pos) };
    }

    /// 重建假设 data[0..start] 仍然是一个合适的堆。
    fn rebuild_tail(&mut self, start: usize) {
        if start == self.len() {
            return;
        }

        let tail_len = self.len() - start;

        #[inline(always)]
        fn log2_fast(x: usize) -> usize {
            (usize::BITS - x.leading_zeros() - 1) as usize
        }

        // `rebuild` 在最坏情况下需要 O(self.len()) 次操作和大约 2 * self.len() 次比较，而重复 `sift_up` 在最坏情况下需要 O(tail_len * log(start)) 次操作和大约 1 * tail_len * log_2(start) 次比较，假设 start >= tail_len。
        // 对于较大的堆，交叉点不再遵循此推理，而是根据经验确定的。
        //
        //
        //
        //
        let better_to_rebuild = if start < tail_len {
            true
        } else if self.len() <= 2048 {
            2 * self.len() < tail_len * log2_fast(start)
        } else {
            2 * self.len() < tail_len * 11
        };

        if better_to_rebuild {
            self.rebuild();
        } else {
            for i in start..self.len() {
                // SAFETY: 索引 `i` 始终小于 self.len()。
                unsafe { self.sift_up(0, i) };
            }
        }
    }

    fn rebuild(&mut self) {
        let mut n = self.len() / 2;
        while n > 0 {
            n -= 1;
            // SAFETY: n starts from self.len() / 2 and goes down to  0.
            //  `!(n < self.len())` 是 `self.len() == 0` 的唯一情况，但是循环条件将其排除在外。
            //
            unsafe { self.sift_down(n) };
        }
    }

    /// 将 `other` 的所有元素移到 `self`，将 `other` 留空。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    ///
    /// let mut a = BinaryHeap::from([-10, 1, 2, 3, 3]);
    /// let mut b = BinaryHeap::from([-20, 5, 43]);
    ///
    /// a.append(&mut b);
    ///
    /// assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
    /// assert!(b.is_empty());
    /// ```
    #[stable(feature = "binary_heap_append", since = "1.11.0")]
    pub fn append(&mut self, other: &mut Self) {
        if self.len() < other.len() {
            swap(self, other);
        }

        let start = self.data.len();

        self.data.append(&mut other.data);

        self.rebuild_tail(start);
    }

    /// 清除二进制堆，按堆顺序返回已删除元素的迭代器。
    /// 如果迭代器在被完全消耗之前被丢弃，它会按照堆顺序丢弃剩余的元素。
    ///
    ///
    /// 返回的迭代器在堆上保留一个可变借用以优化其实现。
    ///
    /// Note:
    /// * `.drain_sorted()` 是 *O*(*n*\* log(*n*))； 比 `.drain()` 慢得多。
    ///   在大多数情况下，应使用后者。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// #![feature(binary_heap_drain_sorted)]
    /// use std::collections::BinaryHeap;
    ///
    /// let mut heap = BinaryHeap::from([1, 2, 3, 4, 5]);
    /// assert_eq!(heap.len(), 5);
    ///
    /// drop(heap.drain_sorted()); // 删除堆顺序中的所有元素
    /// assert_eq!(heap.len(), 0);
    /// ```
    ///
    #[inline]
    #[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
    pub fn drain_sorted(&mut self) -> DrainSorted<'_, T> {
        DrainSorted { inner: self }
    }

    /// 仅保留谓词指定的元素。
    ///
    /// 换句话说，删除所有 `f(&e)` 返回 `false` 的 `e` 元素。
    /// 元素以未排序 (和未指定) 的顺序访问。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    ///
    /// let mut heap = BinaryHeap::from([-10, -5, 1, 2, 4, 13]);
    ///
    /// heap.retain(|x| x % 2 == 0); // 只保留偶数
    ///
    /// assert_eq!(heap.into_sorted_vec(), [-10, 2, 4])
    /// ```
    #[stable(feature = "binary_heap_retain", since = "1.70.0")]
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,
    {
        // rebuild_start 会更新到下面第一个接触到的元素，重建只会对尾部进行。
        //
        let mut guard = RebuildOnDrop { rebuild_from: self.len(), heap: self };
        let mut i = 0;

        guard.heap.data.retain(|e| {
            let keep = f(e);
            if !keep && i < guard.rebuild_from {
                guard.rebuild_from = i;
            }
            i += 1;
            keep
        });
    }
}

impl<T> BinaryHeap<T> {
    /// 返回一个迭代器，以任意顺序访问底层 vector 中的所有值。
    ///
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let heap = BinaryHeap::from([1, 2, 3, 4]);
    ///
    /// // 以任意顺序打印 1，2，3，4
    /// for x in heap.iter() {
    ///     println!("{x}");
    /// }
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn iter(&self) -> Iter<'_, T> {
        Iter { iter: self.data.iter() }
    }

    /// 返回一个迭代器，该迭代器以堆顺序检索元素。
    /// 此方法消耗原始堆。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// #![feature(binary_heap_into_iter_sorted)]
    /// use std::collections::BinaryHeap;
    /// let heap = BinaryHeap::from([1, 2, 3, 4, 5]);
    ///
    /// assert_eq!(heap.into_iter_sorted().take(2).collect::<Vec<_>>(), [5, 4]);
    /// ```
    #[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")]
    pub fn into_iter_sorted(self) -> IntoIterSorted<T> {
        IntoIterSorted { inner: self }
    }

    /// 返回二进制堆中最大的项，如果为空，则返回 `None`。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap = BinaryHeap::new();
    /// assert_eq!(heap.peek(), None);
    ///
    /// heap.push(1);
    /// heap.push(5);
    /// heap.push(2);
    /// assert_eq!(heap.peek(), Some(&5));
    ///
    /// ```
    ///
    /// # 时间复杂度
    ///
    /// 在最坏的情况下，成本为 *O*(1)。
    #[must_use]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn peek(&self) -> Option<&T> {
        self.data.get(0)
    }

    /// 返回二进制堆在不重新分配的情况下可以容纳的元素数。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap = BinaryHeap::with_capacity(100);
    /// assert!(heap.capacity() >= 100);
    /// heap.push(4);
    /// ```
    #[must_use]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn capacity(&self) -> usize {
        self.data.capacity()
    }

    /// 为超过当前长度的至少 `additional` 个元素保留最小容量。
    /// 与 [`reserve`] 不同，这不会故意过度分配以推测性地避免频繁分配。
    ///
    /// 调用 `reserve_exact` 后，容量将大于或等于 `self.len() + additional`。
    /// 如果容量已经足够，则不执行任何操作。
    ///
    /// [`reserve`]: BinaryHeap::reserve
    ///
    /// # Panics
    ///
    /// 如果新容量溢出 [`usize`]，就会出现 panics。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap = BinaryHeap::new();
    /// heap.reserve_exact(100);
    /// assert!(heap.capacity() >= 100);
    /// heap.push(4);
    /// ```
    ///
    /// [`reserve`]: BinaryHeap::reserve
    ///
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn reserve_exact(&mut self, additional: usize) {
        self.data.reserve_exact(additional);
    }

    /// 为超过当前长度的至少 `additional` 个元素保留容量。分配器可以保留更多空间来推测性地避免频繁分配。
    ///
    /// 调用 `reserve` 后，容量将大于或等于 `self.len() + additional`。
    /// 如果容量已经足够，则不执行任何操作。
    ///
    /// # Panics
    ///
    /// 如果新容量溢出 [`usize`]，就会出现 panics。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap = BinaryHeap::new();
    /// heap.reserve(100);
    /// assert!(heap.capacity() >= 100);
    /// heap.push(4);
    /// ```
    ///
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn reserve(&mut self, additional: usize) {
        self.data.reserve(additional);
    }

    /// 尝试为超过当前长度的至少 `additional` 个元素保留最小容量。
    /// 与 [`try_reserve`] 不同，这不会故意过度分配以推测性地避免频繁分配。
    /// 调用 `try_reserve_exact` 后，如果返回 `Ok(())`，则容量将大于或等于 `self.len() + additional`。
    ///
    /// 如果容量已经足够，则不执行任何操作。
    ///
    /// 请注意，分配器可能会给集合提供比其请求更多的空间。
    /// 因此，不能依靠容量来精确地最小化。
    /// 如果希望将来插入，则首选 [`try_reserve`]。
    ///
    /// [`try_reserve`]: BinaryHeap::try_reserve
    ///
    /// # Errors
    ///
    /// 如果容量溢出，或者分配器报告失败，则返回错误。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// use std::collections::TryReserveError;
    ///
    /// fn find_max_slow(data: &[u32]) -> Result<Option<u32>, TryReserveError> {
    ///     let mut heap = BinaryHeap::new();
    ///
    ///     // 预先保留内存，如果不能，则退出
    ///     heap.try_reserve_exact(data.len())?;
    ///
    ///     // 现在我们知道在我们复杂的工作中这不能 OOM
    ///     heap.extend(data.iter());
    ///
    ///     Ok(heap.pop())
    /// }
    /// # find_max_slow(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
    /// ```
    ///
    ///
    #[stable(feature = "try_reserve_2", since = "1.63.0")]
    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
        self.data.try_reserve_exact(additional)
    }

    /// 尝试为超过当前长度的至少 `additional` 个元素保留容量。
    /// 分配器可以保留更多空间来推测性地避免频繁分配。
    /// 调用 `try_reserve` 后，如果返回 `Ok(())`，容量将大于等于 `self.len() + additional`。
    ///
    /// 如果容量已经足够，则不执行任何操作。
    /// 即使发生错误，此方法也会保留内容。
    ///
    /// # Errors
    ///
    /// 如果容量溢出，或者分配器报告失败，则返回错误。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// use std::collections::TryReserveError;
    ///
    /// fn find_max_slow(data: &[u32]) -> Result<Option<u32>, TryReserveError> {
    ///     let mut heap = BinaryHeap::new();
    ///
    ///     // 预先保留内存，如果不能，则退出
    ///     heap.try_reserve(data.len())?;
    ///
    ///     // 现在我们知道在我们复杂的工作中这不能 OOM
    ///     heap.extend(data.iter());
    ///
    ///     Ok(heap.pop())
    /// }
    /// # find_max_slow(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
    /// ```
    ///
    #[stable(feature = "try_reserve_2", since = "1.63.0")]
    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
        self.data.try_reserve(additional)
    }

    /// 丢弃尽可能多的附加容量。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
    ///
    /// assert!(heap.capacity() >= 100);
    /// heap.shrink_to_fit();
    /// assert!(heap.capacity() == 0);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn shrink_to_fit(&mut self) {
        self.data.shrink_to_fit();
    }

    /// 丢弃容量下限。
    ///
    /// 容量将至少保持与长度和提供的值一样大。
    ///
    ///
    /// 如果当前容量小于下限，则为无操作。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
    ///
    /// assert!(heap.capacity() >= 100);
    /// heap.shrink_to(10);
    /// assert!(heap.capacity() >= 10);
    /// ```
    #[inline]
    #[stable(feature = "shrink_to", since = "1.56.0")]
    pub fn shrink_to(&mut self, min_capacity: usize) {
        self.data.shrink_to(min_capacity)
    }

    /// 以任意顺序返回底层 vector 中所有值的切片。
    ///
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// #![feature(binary_heap_as_slice)]
    /// use std::collections::BinaryHeap;
    /// use std::io::{self, Write};
    ///
    /// let heap = BinaryHeap::from([1, 2, 3, 4, 5, 6, 7]);
    ///
    /// io::sink().write(heap.as_slice()).unwrap();
    /// ```
    #[must_use]
    #[unstable(feature = "binary_heap_as_slice", issue = "83659")]
    pub fn as_slice(&self) -> &[T] {
        self.data.as_slice()
    }

    /// 消耗 `BinaryHeap` 并以任意顺序返回底层 vector。
    ///
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let heap = BinaryHeap::from([1, 2, 3, 4, 5, 6, 7]);
    /// let vec = heap.into_vec();
    ///
    /// // 将以一定顺序打印
    /// for x in vec {
    ///     println!("{x}");
    /// }
    /// ```
    #[must_use = "`self` will be dropped if the result is not used"]
    #[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
    pub fn into_vec(self) -> Vec<T> {
        self.into()
    }

    /// 返回二进制堆的长度。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// 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()
    }

    /// 检查二进制堆是否为空。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap = BinaryHeap::new();
    ///
    /// assert!(heap.is_empty());
    ///
    /// heap.push(3);
    /// heap.push(5);
    /// heap.push(1);
    ///
    /// assert!(!heap.is_empty());
    /// ```
    #[must_use]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// 清除二进制堆，以任意顺序返回已删除元素的迭代器。
    /// 如果迭代器在被完全消耗之前被丢弃，它会以任意顺序丢弃剩余的元素。
    ///
    ///
    /// 返回的迭代器在堆上保留一个可变借用以优化其实现。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap = BinaryHeap::from([1, 3]);
    ///
    /// assert!(!heap.is_empty());
    ///
    /// for x in heap.drain() {
    ///     println!("{x}");
    /// }
    ///
    /// assert!(heap.is_empty());
    /// ```
    ///
    #[inline]
    #[stable(feature = "drain", since = "1.6.0")]
    pub fn drain(&mut self) -> Drain<'_, T> {
        Drain { iter: self.data.drain(..) }
    }

    /// 从二进制堆中丢弃所有项。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let mut heap = BinaryHeap::from([1, 3]);
    ///
    /// assert!(!heap.is_empty());
    ///
    /// heap.clear();
    ///
    /// assert!(heap.is_empty());
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn clear(&mut self) {
        self.drain();
    }
}

/// Hole 表示切片中的 hole，即没有有效值的索引 (因为它是从中移出或复制的)。
///
/// 在丢弃时，`Hole` 将通过使用最初删除的值填充 hole 位置来恢复切片。
///
struct Hole<'a, T: 'a> {
    data: &'a mut [T],
    elt: ManuallyDrop<T>,
    pos: usize,
}

impl<'a, T> Hole<'a, T> {
    /// 在索引 `pos` 处创建一个新的 `Hole`。
    ///
    /// 不安全，因为 pos 必须在数据切片内。
    #[inline]
    unsafe fn new(data: &'a mut [T], pos: usize) -> Self {
        debug_assert!(pos < data.len());
        // SAFE: pos 应该在切片内
        let elt = unsafe { ptr::read(data.get_unchecked(pos)) };
        Hole { data, elt: ManuallyDrop::new(elt), pos }
    }

    #[inline]
    fn pos(&self) -> usize {
        self.pos
    }

    /// 返回对已删除元素的引用。
    #[inline]
    fn element(&self) -> &T {
        &self.elt
    }

    /// 返回 `index` 处元素的引用。
    ///
    /// 不安全，因为索引必须在数据切片内且不等于 pos。
    #[inline]
    unsafe fn get(&self, index: usize) -> &T {
        debug_assert!(index != self.pos);
        debug_assert!(index < self.data.len());
        unsafe { self.data.get_unchecked(index) }
    }

    /// 将 hole 移到新位置
    ///
    /// 不安全，因为索引必须在数据切片内且不等于 pos。
    #[inline]
    unsafe fn move_to(&mut self, index: usize) {
        debug_assert!(index != self.pos);
        debug_assert!(index < self.data.len());
        unsafe {
            let ptr = self.data.as_mut_ptr();
            let index_ptr: *const _ = ptr.add(index);
            let hole_ptr = ptr.add(self.pos);
            ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1);
        }
        self.pos = index;
    }
}

impl<T> Drop for Hole<'_, T> {
    #[inline]
    fn drop(&mut self) {
        // 再次填充 hole
        unsafe {
            let pos = self.pos;
            ptr::copy_nonoverlapping(&*self.elt, self.data.get_unchecked_mut(pos), 1);
        }
    }
}

/// `BinaryHeap` 元素上的迭代器。
///
/// 该 `struct` 由 [`BinaryHeap::iter()`] 创建。
/// 有关更多信息，请参见其文档。
///
/// [`iter`]: BinaryHeap::iter
#[must_use = "iterators are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Iter<'a, T: 'a> {
    iter: slice::Iter<'a, T>,
}

#[stable(feature = "collection_debug", since = "1.17.0")]
impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("Iter").field(&self.iter.as_slice()).finish()
    }
}

// FIXME(#26925) 删除以支持 `#[derive(Clone)]`
#[stable(feature = "rust1", since = "1.0.0")]
impl<T> Clone for Iter<'_, T> {
    fn clone(&self) -> Self {
        Iter { iter: self.iter.clone() }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    #[inline]
    fn next(&mut self) -> Option<&'a T> {
        self.iter.next()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }

    #[inline]
    fn last(self) -> Option<&'a T> {
        self.iter.last()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
    #[inline]
    fn next_back(&mut self) -> Option<&'a T> {
        self.iter.next_back()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> ExactSizeIterator for Iter<'_, T> {
    fn is_empty(&self) -> bool {
        self.iter.is_empty()
    }
}

#[stable(feature = "fused", since = "1.26.0")]
impl<T> FusedIterator for Iter<'_, T> {}

/// `BinaryHeap` 元素上的拥有的迭代器。
///
/// 这个 `struct` 由 [`BinaryHeap::into_iter()`] 创建 (由 [`IntoIterator`] trait 提供)。
/// 有关更多信息，请参见其文档。
///
/// [`into_iter`]: BinaryHeap::into_iter
#[stable(feature = "rust1", since = "1.0.0")]
#[derive(Clone)]
pub struct IntoIter<T> {
    iter: vec::IntoIter<T>,
}

#[stable(feature = "collection_debug", since = "1.17.0")]
impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("IntoIter").field(&self.iter.as_slice()).finish()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> Iterator for IntoIter<T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        self.iter.next()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> DoubleEndedIterator for IntoIter<T> {
    #[inline]
    fn next_back(&mut self) -> Option<T> {
        self.iter.next_back()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> ExactSizeIterator for IntoIter<T> {
    fn is_empty(&self) -> bool {
        self.iter.is_empty()
    }
}

#[stable(feature = "fused", since = "1.26.0")]
impl<T> FusedIterator for IntoIter<T> {}

#[stable(feature = "default_iters", since = "1.70.0")]
impl<T> Default for IntoIter<T> {
    /// 创建一个空的 `binary_heap::IntoIter`。
    ///
    /// ```
    /// # use std::collections::binary_heap;
    /// let iter: binary_heap::IntoIter<u8> = Default::default();
    /// assert_eq!(iter.len(), 0);
    /// ```
    fn default() -> Self {
        IntoIter { iter: Default::default() }
    }
}

// 除了以下三个不安全的 traits 的 SAFETY 不变量之外，还可以参考 vec::in_place_collect 模块文档以获得概述
//
#[unstable(issue = "none", feature = "inplace_iteration")]
#[doc(hidden)]
unsafe impl<T> SourceIter for IntoIter<T> {
    type Source = IntoIter<T>;

    #[inline]
    unsafe fn as_inner(&mut self) -> &mut Self::Source {
        self
    }
}

#[unstable(issue = "none", feature = "inplace_iteration")]
#[doc(hidden)]
unsafe impl<I> InPlaceIterable for IntoIter<I> {}

unsafe impl<I> AsVecIntoIter for IntoIter<I> {
    type Item = I;

    fn as_into_iter(&mut self) -> &mut vec::IntoIter<Self::Item> {
        &mut self.iter
    }
}

#[must_use = "iterators are lazy and do nothing unless consumed"]
#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")]
#[derive(Clone, Debug)]
pub struct IntoIterSorted<T> {
    inner: BinaryHeap<T>,
}

#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")]
impl<T: Ord> Iterator for IntoIterSorted<T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        self.inner.pop()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let exact = self.inner.len();
        (exact, Some(exact))
    }
}

#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")]
impl<T: Ord> ExactSizeIterator for IntoIterSorted<T> {}

#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")]
impl<T: Ord> FusedIterator for IntoIterSorted<T> {}

#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<T: Ord> TrustedLen for IntoIterSorted<T> {}

/// `BinaryHeap` 的元素上的 draining 迭代器。
///
/// 该 `struct` 由 [`BinaryHeap::drain()`] 创建。
/// 有关更多信息，请参见其文档。
///
/// [`drain`]: BinaryHeap::drain
#[stable(feature = "drain", since = "1.6.0")]
#[derive(Debug)]
pub struct Drain<'a, T: 'a> {
    iter: vec::Drain<'a, T>,
}

#[stable(feature = "drain", since = "1.6.0")]
impl<T> Iterator for Drain<'_, T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        self.iter.next()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}

#[stable(feature = "drain", since = "1.6.0")]
impl<T> DoubleEndedIterator for Drain<'_, T> {
    #[inline]
    fn next_back(&mut self) -> Option<T> {
        self.iter.next_back()
    }
}

#[stable(feature = "drain", since = "1.6.0")]
impl<T> ExactSizeIterator for Drain<'_, T> {
    fn is_empty(&self) -> bool {
        self.iter.is_empty()
    }
}

#[stable(feature = "fused", since = "1.26.0")]
impl<T> FusedIterator for Drain<'_, T> {}

/// `BinaryHeap` 的元素上的 draining 迭代器。
///
/// 该 `struct` 由 [`BinaryHeap::drain_sorted()`] 创建。
/// 有关更多信息，请参见其文档。
///
/// [`drain_sorted`]: BinaryHeap::drain_sorted
#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
#[derive(Debug)]
pub struct DrainSorted<'a, T: Ord> {
    inner: &'a mut BinaryHeap<T>,
}

#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
impl<'a, T: Ord> Drop for DrainSorted<'a, T> {
    /// 按堆顺序删除堆元素。
    fn drop(&mut self) {
        struct DropGuard<'r, 'a, T: Ord>(&'r mut DrainSorted<'a, T>);

        impl<'r, 'a, T: Ord> Drop for DropGuard<'r, 'a, T> {
            fn drop(&mut self) {
                while self.0.inner.pop().is_some() {}
            }
        }

        while let Some(item) = self.inner.pop() {
            let guard = DropGuard(self);
            drop(item);
            mem::forget(guard);
        }
    }
}

#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
impl<T: Ord> Iterator for DrainSorted<'_, T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        self.inner.pop()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let exact = self.inner.len();
        (exact, Some(exact))
    }
}

#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
impl<T: Ord> ExactSizeIterator for DrainSorted<'_, T> {}

#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
impl<T: Ord> FusedIterator for DrainSorted<'_, T> {}

#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<T: Ord> TrustedLen for DrainSorted<'_, T> {}

#[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
impl<T: Ord> From<Vec<T>> for BinaryHeap<T> {
    /// 将 `Vec<T>` 转换为 `BinaryHeap<T>`。
    ///
    /// 此转换发生在原地，并且具有 *O*(*n*) 时间复杂度。
    fn from(vec: Vec<T>) -> BinaryHeap<T> {
        let mut heap = BinaryHeap { data: vec };
        heap.rebuild();
        heap
    }
}

#[stable(feature = "std_collections_from_array", since = "1.56.0")]
impl<T: Ord, const N: usize> From<[T; N]> for BinaryHeap<T> {
    /// ```
    /// use std::collections::BinaryHeap;
    ///
    /// let mut h1 = BinaryHeap::from([1, 4, 2, 3]);
    /// let mut h2: BinaryHeap<_> = [1, 4, 2, 3].into();
    /// while let Some((a, b)) = h1.pop().zip(h2.pop()) {
    ///     assert_eq!(a, b);
    /// }
    /// ```
    fn from(arr: [T; N]) -> Self {
        Self::from_iter(arr)
    }
}

#[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
impl<T> From<BinaryHeap<T>> for Vec<T> {
    /// 将 `BinaryHeap<T>` 转换为 `Vec<T>`。
    ///
    /// 这种转换不需要数据移动或分配，并且具有恒定的时间复杂度。
    ///
    fn from(heap: BinaryHeap<T>) -> Vec<T> {
        heap.data
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Ord> FromIterator<T> for BinaryHeap<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BinaryHeap<T> {
        BinaryHeap::from(iter.into_iter().collect::<Vec<_>>())
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> IntoIterator for BinaryHeap<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    /// 创建一个消耗迭代器，即一个将任意值以任意顺序移出二进制堆的迭代器。
    /// 调用此后不能使用二进制堆。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// use std::collections::BinaryHeap;
    /// let heap = BinaryHeap::from([1, 2, 3, 4]);
    ///
    /// // 以任意顺序打印 1，2，3，4
    /// for x in heap.into_iter() {
    ///     // x 的类型为 i32，不是 &i32
    ///     println!("{x}");
    /// }
    /// ```
    ///
    fn into_iter(self) -> IntoIter<T> {
        IntoIter { iter: self.data.into_iter() }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a BinaryHeap<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Iter<'a, T> {
        self.iter()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Ord> Extend<T> for BinaryHeap<T> {
    #[inline]
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        let guard = RebuildOnDrop { rebuild_from: self.len(), heap: self };
        guard.heap.data.extend(iter);
    }

    #[inline]
    fn extend_one(&mut self, item: T) {
        self.push(item);
    }

    #[inline]
    fn extend_reserve(&mut self, additional: usize) {
        self.reserve(additional);
    }
}

#[stable(feature = "extend_ref", since = "1.2.0")]
impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BinaryHeap<T> {
    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
        self.extend(iter.into_iter().cloned());
    }

    #[inline]
    fn extend_one(&mut self, &item: &'a T) {
        self.push(item);
    }

    #[inline]
    fn extend_reserve(&mut self, additional: usize) {
        self.reserve(additional);
    }
}