rust_algorithms/data_structures/

heap.rs

//! Binary heap (uyum) — prioritetli navbat.

/// Min-heap: eng kichik element har doim tepada.
///
/// **G'oya:** to'liq binar daraxtni **massivda** saqlaymiz. `i` -indeksdagi tugun uchun:
/// - ota: `(i - 1) / 2`
/// - chap farzand: `2i + 1`, o'ng farzand: `2i + 2`
///
/// Yagona qoida (heap sharti): **ota farzandidan katta emas**.
/// Shu qoidani buzmaslik uchun ikkita amal bor: `sift_up` (qo'shishda) va
/// `sift_down` (o'chirishda). Ikkalasi ham daraxt balandligi bo'ylab yuradi → O(log n).
///
/// ```text
///        1              massiv: [1, 3, 5, 7, 9, 8]
///      /   \
///     3     5           ota(4) = (4-1)/2 = 1  → qiymati 3
///    / \   /
///   7   9 8
/// ```
///
/// **Qayerda ishlatiladi:** Dijkstra, A*, Huffman, "eng katta K ta element",
/// vazifalar rejalashtiruvchisi (scheduler).
///
/// > Max-heap kerakmi? `std::cmp::Reverse` bilan o'rang yoki qiymatlarni manfiylang.
///
/// # Misol
/// ```
/// use rust_algorithms::data_structures::MinHeap;
///
/// let mut h = MinHeap::new();
/// for x in [5, 1, 8, 3] {
///     h.push(x);
/// }
/// assert_eq!(h.peek(), Some(&1));
/// assert_eq!(h.pop(), Some(1));
/// assert_eq!(h.pop(), Some(3));
/// assert_eq!(h.len(), 2);
/// ```
#[derive(Debug, Clone, Default)]
pub struct MinHeap<T: Ord> {
    data: Vec<T>,
}

impl<T: Ord> MinHeap<T> {
    /// Bo'sh heap.
    pub fn new() -> Self {
        Self { data: Vec::new() }
    }

    /// Tayyor vektordan heap quradi — **O(n)** (n log n emas!).
    ///
    /// Pastdan yuqoriga `sift_down` qilish n log n emas, chiziqli vaqt beradi:
    /// tugunlarning yarmi bargda (0 qadam), choragi bir qavat yuqorida (1 qadam)…
    ///
    /// # Misol
    /// ```
    /// use rust_algorithms::data_structures::MinHeap;
    ///
    /// let h = MinHeap::heapify(vec![9, 4, 7, 1, 2]);
    /// assert_eq!(h.peek(), Some(&1));
    /// ```
    pub fn heapify(data: Vec<T>) -> Self {
        let mut h = Self { data };
        for i in (0..h.data.len() / 2).rev() {
            h.sift_down(i);
        }
        h
    }

    /// Element qo'shadi. O(log n).
    pub fn push(&mut self, item: T) {
        self.data.push(item);
        self.sift_up(self.data.len() - 1);
    }

    /// Eng kichik elementni olib chiqadi. O(log n).
    pub fn pop(&mut self) -> Option<T> {
        if self.data.is_empty() {
            return None;
        }
        let oxirgi = self.data.len() - 1;
        self.data.swap(0, oxirgi);
        let min = self.data.pop();
        if !self.data.is_empty() {
            self.sift_down(0);
        }
        min
    }

    /// Eng kichik elementga qaraydi. O(1).
    pub fn peek(&self) -> Option<&T> {
        self.data.first()
    }

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

    /// Bo'shmi?
    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    /// Heapni tartiblangan vektorga aylantiradi (heap sort). O(n log n).
    pub fn into_sorted_vec(mut self) -> Vec<T> {
        let mut out = Vec::with_capacity(self.data.len());
        while let Some(x) = self.pop() {
            out.push(x);
        }
        out
    }

    /// Yangi qo'shilgan elementni yuqoriga ko'taradi.
    fn sift_up(&mut self, mut i: usize) {
        while i > 0 {
            let ota = (i - 1) / 2;
            if self.data[i] >= self.data[ota] {
                break;
            }
            self.data.swap(i, ota);
            i = ota;
        }
    }

    /// Ildizdagi elementni pastga tushiradi.
    fn sift_down(&mut self, mut i: usize) {
        let n = self.data.len();
        loop {
            let chap = 2 * i + 1;
            if chap >= n {
                break;
            }
            let ong = chap + 1;
            let mut kichik = chap;
            if ong < n && self.data[ong] < self.data[chap] {
                kichik = ong;
            }
            if self.data[i] <= self.data[kichik] {
                break;
            }
            self.data.swap(i, kichik);
            i = kichik;
        }
    }
}

impl<T: Ord> FromIterator<T> for MinHeap<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        Self::heapify(iter.into_iter().collect())
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::util::Rng;

    #[test]
    fn tartibda_chiqaradi() {
        let mut rng = Rng::new(101);
        let sonlar = rng.vec(500, -1000, 1000);
        let heap: MinHeap<i64> = sonlar.iter().cloned().collect();
        let chiqish = heap.into_sorted_vec();

        let mut kutilgan = sonlar.clone();
        kutilgan.sort_unstable();
        assert_eq!(chiqish, kutilgan);
    }

    #[test]
    fn bosh_heap() {
        let mut h: MinHeap<i32> = MinHeap::new();
        assert!(h.is_empty());
        assert_eq!(h.pop(), None);
        assert_eq!(h.peek(), None);
    }

    #[test]
    fn push_pop_aralash() {
        let mut h = MinHeap::new();
        h.push(5);
        h.push(3);
        assert_eq!(h.pop(), Some(3));
        h.push(1);
        h.push(4);
        assert_eq!(h.pop(), Some(1));
        assert_eq!(h.pop(), Some(4));
        assert_eq!(h.pop(), Some(5));
        assert_eq!(h.pop(), None);
    }

    #[test]
    fn heap_sharti_saqlanadi() {
        let mut rng = Rng::new(202);
        let mut h = MinHeap::new();
        for _ in 0..200 {
            h.push(rng.range(0, 100));
        }
        // har bir ota farzandlaridan katta emas
        for i in 0..h.data.len() {
            for f in [2 * i + 1, 2 * i + 2] {
                if f < h.data.len() {
                    assert!(h.data[i] <= h.data[f]);
                }
            }
        }
    }
}