Struct MinHeap 

pub struct MinHeap<T: Ord> { /* private fields */ }

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).

       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);

Implementations

impl<T: Ord> MinHeap<T>

pub fn new() -> Self

Bo’sh heap.

pub fn heapify(data: Vec<T>) -> Self

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 push(&mut self, item: T)

Element qo’shadi. O(log n).

pub fn pop(&mut self) -> Option<T>

Eng kichik elementni olib chiqadi. O(log n).

pub fn peek(&self) -> Option<&T>

Eng kichik elementga qaraydi. O(1).

pub fn len(&self) -> usize

Elementlar soni.

pub fn is_empty(&self) -> bool

Bo’shmi?

pub fn into_sorted_vec(self) -> Vec<T>

Heapni tartiblangan vektorga aylantiradi (heap sort). O(n log n).

Trait Implementations

impl<T: Clone + Ord> Clone for MinHeap<T>

fn clone(&self) -> MinHeap<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Ord> Debug for MinHeap<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Default + Ord> Default for MinHeap<T>

fn default() -> MinHeap<T>

Returns the “default value” for a type.

impl<T: Ord> FromIterator<T> for MinHeap<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.