Uyum (Heap)

def chap_bola(i):
    return 2 * i + 1

def ong_bola(i):
    return 2 * i + 2

def ota(i):
    return (i - 1) // 2


# Tekshirib ko'ramiz: uyum = [3, 5, 8, 10, 7, 9]
print(f"Ildiz [0] ning bolalari: [{chap_bola(0)}] va [{ong_bola(0)}]")
print(f"[1] ning bolalari:       [{chap_bola(1)}] va [{ong_bola(1)}]")
print(f"[4] ning otasi:          [{ota(4)}]")

class MinUyum:
    """Eng kichik element har doim ildizda turadi."""

    def __init__(self):
        self._elementlar = []

    # ---------- yordamchi indekslar ----------

    @staticmethod
    def _ota(i):
        return (i - 1) // 2

    @staticmethod
    def _chap(i):
        return 2 * i + 1

    @staticmethod
    def _ong(i):
        return 2 * i + 2

    def _almashtir(self, i, j):
        self._elementlar[i], self._elementlar[j] = self._elementlar[j], self._elementlar[i]

    # ---------- asosiy amallar ----------

    def qosh(self, qiymat):
        """Element qo'shadi. O(log n)."""
        self._elementlar.append(qiymat)
        self._yuqoriga_kotar(len(self._elementlar) - 1)

    def eng_kichigini_ol(self):
        """Eng kichik elementni olib tashlaydi va qaytaradi. O(log n)."""
        if not self._elementlar:
            raise IndexError("Uyum bo'sh")

        eng_kichik = self._elementlar[0]
        oxirgi = self._elementlar.pop()

        if self._elementlar:
            self._elementlar[0] = oxirgi
            self._pastga_tushir(0)

        return eng_kichik

    def eng_kichigini_kor(self):
        """Olmasdan qaraydi. O(1)."""
        if not self._elementlar:
            raise IndexError("Uyum bo'sh")
        return self._elementlar[0]

    # ---------- muvozanatni tiklash ----------

    def _yuqoriga_kotar(self, i):
        """Yangi elementni o'z o'rniga ko'taradi (sift up)."""
        while i > 0:
            ota_indeks = self._ota(i)
            if self._elementlar[i] >= self._elementlar[ota_indeks]:
                break
            self._almashtir(i, ota_indeks)
            i = ota_indeks

    def _pastga_tushir(self, i):
        """Ildizdagi elementni o'z o'rniga tushiradi (sift down)."""
        soni = len(self._elementlar)

        while True:
            eng_kichik = i
            chap, ong = self._chap(i), self._ong(i)

            if chap < soni and self._elementlar[chap] < self._elementlar[eng_kichik]:
                eng_kichik = chap
            if ong < soni and self._elementlar[ong] < self._elementlar[eng_kichik]:
                eng_kichik = ong

            if eng_kichik == i:
                break

            self._almashtir(i, eng_kichik)
            i = eng_kichik

    def __len__(self):
        return len(self._elementlar)

    def __str__(self):
        return str(self._elementlar)

uyum = MinUyum()

for son in [10, 4, 15, 20, 1, 8]:
    uyum.qosh(son)
    print(f"{son:>3} qo'shildi -> {uyum}")

print("\nO'sish tartibida chiqaramiz:")
while len(uyum):
    print(uyum.eng_kichigini_ol(), end=" ")
print()

import heapq

uyum = []

heapq.heappush(uyum, 10)
heapq.heappush(uyum, 4)
heapq.heappush(uyum, 15)
heapq.heappush(uyum, 1)

print("Uyum:", uyum)
print("Eng kichik:", uyum[0])          # O(1) - olmasdan qarash
print("Olindi:", heapq.heappop(uyum))  # O(log n)

# Mavjud ro'yxatni uyumga aylantirish - O(n), sikldan tezroq!
sonlar = [10, 4, 15, 20, 1, 8]
heapq.heapify(sonlar)
print("Heapify:", sonlar)

# Eng katta / eng kichik N ta element
baholar = [85, 92, 78, 95, 88, 71, 99]
print("Eng yuqori 3 ta:", heapq.nlargest(3, baholar))
print("Eng past 3 ta:  ", heapq.nsmallest(3, baholar))

import heapq

max_uyum = []
for baho in [85, 92, 78, 95]:
    heapq.heappush(max_uyum, -baho)        # manfiy qilib saqlaymiz

print("Eng yuqori baho:", -heapq.heappop(max_uyum))
print("Keyingisi:      ", -heapq.heappop(max_uyum))

import heapq
from dataclasses import dataclass, field


@dataclass(order=True)
class Vazifa:
    prioritet: int
    tartib: int
    nomi: str = field(compare=False)


class VazifalarNavbati:
    def __init__(self):
        self._uyum = []
        self._hisoblagich = 0

    def qosh(self, nomi, prioritet):
        heapq.heappush(self._uyum, Vazifa(prioritet, self._hisoblagich, nomi))
        self._hisoblagich += 1

    def keyingisi(self):
        if not self._uyum:
            return None
        return heapq.heappop(self._uyum).nomi

    def __len__(self):
        return len(self._uyum)


navbat = VazifalarNavbati()
navbat.qosh("Hisobotni yuborish", 2)
navbat.qosh("Serverni tiklash", 0)
navbat.qosh("Emailga javob berish", 3)
navbat.qosh("Xatolikni tuzatish", 1)

print("Bajarish tartibi:")
while len(navbat):
    print("  -", navbat.keyingisi())

def uyum_bilan_sarala(sonlar):
    """Heap sort. O(n log n) vaqt, O(1) qo'shimcha xotira."""
    massiv = list(sonlar)
    n = len(massiv)

    def tushir(chegara, i):
        while True:
            eng_katta = i
            chap, ong = 2 * i + 1, 2 * i + 2

            if chap < chegara and massiv[chap] > massiv[eng_katta]:
                eng_katta = chap
            if ong < chegara and massiv[ong] > massiv[eng_katta]:
                eng_katta = ong
            if eng_katta == i:
                break

            massiv[i], massiv[eng_katta] = massiv[eng_katta], massiv[i]
            i = eng_katta

    # 1-bosqich: max-uyum quramiz  O(n)
    for i in range(n // 2 - 1, -1, -1):
        tushir(n, i)

    # 2-bosqich: eng kattani oxirga surib boramiz  O(n log n)
    for oxir in range(n - 1, 0, -1):
        massiv[0], massiv[oxir] = massiv[oxir], massiv[0]
        tushir(oxir, 0)

    return massiv


print(uyum_bilan_sarala([10, 4, 15, 20, 1, 8, 3]))

import heapq


class MedianaKuzatuvchi:
    """Oqimga kelayotgan sonlarning medianasini O(log n) da yangilaydi."""

    def __init__(self):
        self._kichik_yarim = []      # max-uyum (manfiy qiymatlar bilan)
        self._katta_yarim = []       # min-uyum

    def qosh(self, son):
        heapq.heappush(self._kichik_yarim, -son)

        # Kichik yarimning eng kattasini katta yarimga o'tkazamiz
        heapq.heappush(self._katta_yarim, -heapq.heappop(self._kichik_yarim))

        # Muvozanatni saqlaymiz
        if len(self._katta_yarim) > len(self._kichik_yarim):
            heapq.heappush(self._kichik_yarim, -heapq.heappop(self._katta_yarim))

    def mediana(self):
        if not self._kichik_yarim:
            return None
        if len(self._kichik_yarim) > len(self._katta_yarim):
            return -self._kichik_yarim[0]
        return (-self._kichik_yarim[0] + self._katta_yarim[0]) / 2


kuzatuvchi = MedianaKuzatuvchi()
for son in [5, 15, 1, 3, 8, 7, 9, 10, 6, 11, 4]:
    kuzatuvchi.qosh(son)
    print(f"{son:>3} qo'shildi -> mediana = {kuzatuvchi.mediana()}")