# فصل ۰۴ — `heap` و `priority queue`

<div dir="rtl">

# فصل ۰۴ — `heap` و `priority queue`

## در این فصل چه یاد می‌گیری

`BST` برای «این کلید هست؟» ساخته شده بود. ولی خیلی از برنامه‌ها سؤالِ دیگری می‌پرسند و آن را **بارها** می‌پرسند: **«کوچک‌ترین چیست؟ حالا برش دار. حالا کوچک‌ترینِ بعدی چیست؟»**

برای همین یک ساختارِ اختصاصی هست که فقط همین را ارزان می‌کند و **هیچ گره و ارجاعی هم لازم ندارد** — یک `list` ساده که خودش درخت است. اسمش `heap` است.

بعد اندازه‌اش می‌گیریم و یک نتیجهٔ غیرمنتظره درمی‌آید: **روی ورودیِ تصادفی، `n` درج ستونِ نسبتِ `2.02` می‌دهد** — یعنی هر درج **به‌طورِ متوسط** هزینهٔ ثابت دارد — ولی **`n` درج به‌علاوهٔ `n` برداشت ستونِ `2.19`**. تمامِ `log n` این ساختار در برداشتن است، نه در گذاشتن.

**و بعد همان درج را روی ورودیِ نزولی می‌بریم و همان `2.02` می‌شود `2.20`.** «به‌طورِ متوسط» یک قید است، نه یک تعارف — و این فصل هزینه‌اش را با عدد نشان می‌دهد.

![یک ردیف خانهٔ شماره‌دار در کنارِ درختی که هر گره‌اش دقیقاً به یکی از همان خانه‌ها وصل شده است](/lesson-assets/t5-s04-heap/prompt/01-image-array-as-tree.png)

آخر این فصل می‌توانی:

- خاصیتِ `heap` را روی یک `list` با دست وارسی کنی
- بالا بردن و پایین آوردنِ یک عنصر را خودت بنویسی
- `k` بزرگ‌ترین را **بدونِ مرتب کردنِ همه** پیدا کنی و هزینه‌اش را بشماری
- بگویی چرا یک `tuple` در `heap` می‌تواند ناگهان `TypeError` بدهد

## قبل از شروع

**از فصلِ ۲:** شماره‌گذاریِ `level-order` — گرهٔ `i` و فرزندانش. **همان شماره‌گذاری این‌جا تبدیل به کلِ ساختار می‌شود.**

**از ترمِ ۲ فصلِ ۳:** هزینهٔ `amortised` و اینکه میانگینِ بلندمدت با بدترین تکِ عملیات یکی نیست. **از ترمِ ۴ فصلِ ۸:** `sorted` و اینکه از هر چیزی که خودت بنویسی سریع‌تر است.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | حدودِ یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-5-trees-and-graphs/session-04-heap.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. درختی که هیچ ارجاعی ندارد

در فصلِ ۲ دیدیم که `level-order` روی درختِ کامل، گره‌ها را به‌ترتیبِ `1, 2, 3, …` می‌دهد. **حالا برعکسش را انجام می‌دهیم:** یک `list` بردار، خانهٔ `i`ام را گرهِ `i`ام حساب کن، و فرزندانش را از روی اندیس پیدا کن.

</div>

```python
def parent(i):
    return (i - 1) // 2


def children(i):
    return 2 * i + 1, 2 * i + 2


small = [3, 5, 8, 9, 6, 11]
for i in range(len(small)):
    left, right = children(i)
    kids = [small[j] for j in (left, right) if j < len(small)]
    print(f"خانهٔ {i}: مقدار {small[i]:>2}  ·  فرزندان {kids}")
print("\nهر پدر از فرزندانش کوچک‌تر است؟",
      all(small[i] <= small[j]
          for i in range(len(small)) for j in children(i) if j < len(small)))
```

```text
خانهٔ 0: مقدار  3  ·  فرزندان [5, 8]
خانهٔ 1: مقدار  5  ·  فرزندان [9, 6]
خانهٔ 2: مقدار  8  ·  فرزندان [11]
خانهٔ 3: مقدار  9  ·  فرزندان []
خانهٔ 4: مقدار  6  ·  فرزندان []
خانهٔ 5: مقدار 11  ·  فرزندان []

هر پدر از فرزندانش کوچک‌تر است؟ True
```

<div dir="rtl">

**هیچ گره‌ای، هیچ ارجاعی، هیچ `None`ی.** یک `list` شش‌خانه‌ای، و درخت فقط در حسابِ اندیس وجود دارد. **این یعنی همهٔ مزایای حافظهٔ پیوستهٔ ترمِ ۲ فصلِ ۱ سرِ جایشان می‌مانند** — چیزی که هیچ‌کدام از درخت‌های دو فصلِ قبل نداشتند.

و سطرِ آخر، **خاصیتِ `heap`** را وارسی می‌کند: هر پدر از هر دو فرزندش کوچک‌تر (یا مساوی) است. **دقت کن این خیلی ضعیف‌تر از مرتب‌بودن است:** خانهٔ ۱ مقدارِ `5` دارد و خانهٔ ۴ مقدارِ `6` — درست، ولی خانهٔ ۳ مقدارِ `9` دارد که از هر دویشان بزرگ‌تر است. **`heap` فقط دربارهٔ رابطهٔ پدر و فرزند حرف می‌زند و دربارهٔ هم‌سطح‌ها هیچ نمی‌گوید.** و همین ضعف است که ارزانش می‌کند.

## ۲. بالا بردن: درج

عضوِ تازه ته `list` اضافه می‌شود و بعد **تا جایی بالا می‌رود که از پدرش کوچک‌تر نباشد.** بیشترین راهی که می‌تواند برود، از یک برگ تا ریشه است — یعنی ارتفاعِ درخت.

</div>

```python
def sift_up(h, i, stats):
    """گرهٔ تازه را تا جایی بالا می‌برد که از پدرش کوچک‌تر نباشد."""
    while i > 0:
        up = parent(i)
        stats[0] += 1
        if h[i] < h[up]:
            h[i], h[up] = h[up], h[i]
            i = up
        else:
            return


def heap_push(h, value, stats):
    h.append(value)
    sift_up(h, len(h) - 1, stats)


stats = [0]
demo = []
for v in (9, 6, 11, 3, 8, 5):
    heap_push(demo, v, stats)
    print(f"push {v:>2} → {demo}")
print("مقایسه‌های کل:", stats[0], " · کمینه همیشه در خانهٔ صفر:", demo[0])
```

```text
push  9 → [9]
push  6 → [6, 9]
push 11 → [6, 9, 11]
push  3 → [3, 6, 11, 9]
push  8 → [3, 6, 11, 9, 8]
push  5 → [3, 6, 5, 9, 8, 11]
مقایسه‌های کل: 7  · کمینه همیشه در خانهٔ صفر: 3
```

<div dir="rtl">

**شش درج، هفت مقایسه.** یعنی به‌طورِ متوسط کمی بیشتر از یکی به‌ازای هر درج — نه چیزی شبیهِ `log n`. سطرِ چهارم را ببین: `3` از ته `list` تا خانهٔ صفر بالا رفت و دو مقایسه خورد. ولی بیشترِ درج‌ها با **یک** مقایسه تمام شدند، چون عضوِ تازه معمولاً بزرگ است و همان اولین مقایسه نگهش می‌دارد.

## ۳. پایین آوردن: برداشتنِ کمینه

کمینه همیشه در خانهٔ صفر است، پس **خواندنش رایگان است**. ولی **برداشتنش** یعنی خانهٔ صفر خالی می‌شود و باید پرش کرد: آخرین عضو را می‌گذاریم آن‌جا و **تا جایی پایینش می‌بریم که از هر دو فرزندش کوچک‌تر شود.**

</div>

```python
def sift_down(h, i, stats):
    """گرهٔ ریشه را تا جایی پایین می‌برد که از هر دو فرزندش کوچک‌تر باشد."""
    n = len(h)
    while True:
        left, right = children(i)
        best = i
        if left < n:
            stats[0] += 1
            if h[left] < h[best]:
                best = left
        if right < n:
            stats[0] += 1
            if h[right] < h[best]:
                best = right
        if best == i:
            return
        h[i], h[best] = h[best], h[i]
        i = best


def heap_pop(h, stats):
    """کوچک‌ترین را برمی‌دارد، آخری را جایش می‌گذارد و پایینش می‌برد."""
    top = h[0]
    last = h.pop()
    if h:
        h[0] = last
        sift_down(h, 0, stats)
    return top


order = []
while demo:
    order.append(heap_pop(demo, stats))
print("ترتیبِ بیرون آمدن:", order)
print("همان چیزی است که sorted می‌دهد؟", order == sorted([9, 6, 11, 3, 8, 5]))
```

```text
ترتیبِ بیرون آمدن: [3, 5, 6, 8, 9, 11]
همان چیزی است که sorted می‌دهد؟ True
```

<div dir="rtl">

**اگر پشتِ سرِ هم همه را برداری، مرتب بیرون می‌آیند.** این یک الگوریتمِ مرتب‌سازیِ کامل است و اسمِ خودش را هم دارد. **ولی نکتهٔ اصلیِ `heap` این نیست**؛ نکته‌اش این است که لازم نیست همه را برداری. **می‌توانی فقط سه‌تای اول را بگیری و بروی** — و آن‌وقت هزینهٔ مرتب‌کردنِ بقیه را اصلاً نداده‌ای.

## ۴. تفاوتِ درج و برداشت، با عدد

> 🤔 **اول حدس بزن:** دو جدول می‌آید. اولی هزینهٔ `n` درج است و دومی هزینهٔ `n` درج به‌علاوهٔ `n` برداشت. **برای هر کدام ستونِ نسبت را حدس بزن** و بنویس، بعد جدول‌ها را ببین.

</div>

```python
rng = random.Random(SEED)
LADDER = [1_000, 2_000, 4_000, 8_000]
pools = {n: [rng.randrange(10 ** 6) for _ in range(n)] for n in LADDER}
print("سه عددِ اول:", pools[1_000][:3])


def push_cost(values):
    stats = [0]
    h = []
    for v in values:
        heap_push(h, v, stats)
    return stats[0]


def push_pop_cost(values):
    stats = [0]
    h = []
    for v in values:
        heap_push(h, v, stats)
    while h:
        heap_pop(h, stats)
    return stats[0]


print("\n— فقط n درج")
table([(n, push_cost(pools[n])) for n in LADDER], "مقایسه", ",d")
print("\n— n درج به‌علاوهٔ n برداشت")
table([(n, push_pop_cost(pools[n])) for n in LADDER], "مقایسه", ",d")
```

```text
سه عددِ اول: [815965, 462141, 122526]

— فقط n درج
         n            مقایسه     نسبت به سطر قبل
     1,000             2,163                   —
     2,000             4,509                2.08
     4,000             9,051                2.01
     8,000            18,265                2.02

— n درج به‌علاوهٔ n برداشت
         n            مقایسه     نسبت به سطر قبل
     1,000            17,111                   —
     2,000            38,424                2.25
     4,000            84,936                2.21
     8,000           186,043                2.19
```

<div dir="rtl">

**دو ستونِ نسبت، و فاصله‌شان کوچک ولی تعیین‌کننده است.**

جدولِ اول `2.02` است، یعنی **خطی**: `8,000` درج فقط `18,265` مقایسه خورد — کمی بیشتر از دو مقایسه به‌ازای هر درج، و این عدد با بزرگ‌تر شدنِ `n` رشد نمی‌کند. **درجِ تک می‌تواند تا ریشه بالا برود، ولی روی این ورودی بیشترِ درج‌ها همان اولین مقایسه متوقفشان می‌کند.**

جدولِ دوم `2.25`، `2.21`، `2.19` است — **کمی بالای `2` و آرام‌آرام به سمتِ `2`.** این شکلِ `O(n log n)` است: کارِ خطی، ضربدرِ یک عاملِ کندرشد که با هر دو برابر شدنِ `n` فقط یک واحد بیشتر می‌شود. **و برداشتن است که این عامل را می‌آورد**، چون بر خلافِ درج، `sift_down` تقریباً همیشه تا ته پایین می‌رود: عضوی که از ته `list` برداشته‌ایم معمولاً بزرگ است و جایش هم ته درخت است.

## ۵. همان درج، دو ورودیِ دیگر

جدولِ بالا روی **ورودیِ تصادفی** گرفته شد و همان‌جا هم گفتیم «به‌طورِ متوسط». **ترمِ ۳ فصلِ ۴ یاد داد که این قید را نباید سرسری رد کرد** و فصلِ قبل نشان داد ورودیِ مرتب چطور یک ساختارِ سالم را زمین می‌زند.

> 🤔 **اول حدس بزن:** همان `push_cost`، این بار روی `list(range(n))` (صعودی) و `list(range(n, 0, -1))` (نزولی). **برای هر دو ستونِ نسبت را بنویس** — و مخصوصاً بنویس کدام‌یک برای یک `heap`ِ **کمینه** بدترین است و چرا.

</div>

```python
print("— n درج، ورودیِ صعودی")
table([(n, push_cost(list(range(n)))) for n in LADDER], "مقایسه", ",d")
print("\n— n درج، ورودیِ نزولی")
table([(n, push_cost(list(range(n, 0, -1)))) for n in LADDER], "مقایسه", ",d")
```

```text
— n درج، ورودیِ صعودی
         n            مقایسه     نسبت به سطر قبل
     1,000               999                   —
     2,000             1,999                2.00
     4,000             3,999                2.00
     8,000             7,999                2.00

— n درج، ورودیِ نزولی
         n            مقایسه     نسبت به سطر قبل
     1,000             7,987                   —
     2,000            17,964                2.25
     4,000            39,917                2.22
     8,000            87,822                2.20
```

<div dir="rtl">

**سه ورودی، سه جواب، یک کد.**

- **صعودی: دقیقاً `n - 1` مقایسه**، نسبتِ `2.00` — `O(n)`. هر عضوِ تازه از همه بزرگ‌تر است، پس همان اولین مقایسه نگهش می‌دارد. **بهترین حالت.**
- **تصادفی: `18,265` در `n = 8,000`**، نسبت `2.02` — باز هم `O(n)`، فقط با ثابتِ بزرگ‌تر.
- **نزولی: `87,822` در همان `n`**، نسبت `2.25`، `2.22`، `2.20` — **همان شکلِ `O(n log n)`ِ جدولِ درج‌به‌علاوه‌برداشت.** هر عضوِ تازه از همه کوچک‌تر است، پس `sift_up` هر بار تا ریشه بالا می‌رود و هزینهٔ هر درج ارتفاعِ درخت می‌شود، نه یک مقایسه.

**پس آن `O(1)`ِ درج، «حالتِ متوسط» است — نه `amortised`.** `amortised`ِ ترمِ ۲ فصلِ ۳ یک **تضمین** است روی هر دنبالهٔ عملیات: `n` بار `append` روی هم `O(n)` است، **هر ورودی‌ای که بدهی**. **حالتِ متوسط** فقط یک میانگین روی ورودی‌های تصادفی است، و ستونِ آخر نشان داد یک ورودیِ خاص می‌تواند از آن بیرون بزند. **`heap` از نوعِ دوم است** — به‌همین دلیل ترمِ ۶ فصلِ ۲ برای خانهٔ «افزودن»ِ `heap` هر سه عدد را می‌نویسد.

> 💡 **نکته:** برعکسِ `BST` فصلِ قبل، این بدترین حالت فاجعه نیست: آن‌جا **مرتبهٔ تکِ عملیات** از `log n` به `n` می‌افتاد، ولی این‌جا هیچ درجی از `O(log n)` بدتر نمی‌شود. **تفاوتِ `2.02` و `2.20` در `n = 8,000` حدودِ پنج برابر کارِ بیشتر است — نه صد و سی برابرِ فصلِ ۳.**

## ۶. `k` بزرگ‌ترین، بدونِ مرتب کردنِ همه

سؤالِ واقعیِ خیلی از برنامه‌ها این است: **از میانِ `n` چیز، ده تای بزرگ‌تر کدام‌اند؟** راهِ آشکار این است که همه را مرتب کنی و ده تای اول را برداری. راهِ `heap` این است که **فقط یک `heap` ده‌تایی نگه داری**: هر عددِ تازه را با کوچک‌ترینِ آن ده‌تا مقایسه کن؛ اگر بزرگ‌تر بود جایش را بگیرد، وگرنه دور بریزش.

> 🤔 **اول حدس بزن:** با ثابت ماندنِ `k` و دو برابر شدنِ `n`، ستونِ نسبتِ این روش چه عددی می‌دهد؟ و اگر `n` را ثابت نگه داریم و **`k` را هشت برابر کنیم**، هزینه چند برابر می‌شود؟ **هر دو را بنویس**، بعد جدول‌ها را ببین.

</div>

```python
def k_largest(values, k, stats):
    """heapی به اندازهٔ k نگه می‌دارد: هر عددِ تازه فقط با کوچک‌ترینِ آن مقایسه می‌شود."""
    h = []
    for v in values:
        if len(h) < k:
            heap_push(h, v, stats)
            continue
        stats[0] += 1
        if v > h[0]:
            heap_pop(h, stats)
            heap_push(h, v, stats)
    return sorted(h, reverse=True)


K = 10
mine = k_largest(pools[8_000], K, [0])
print("ده تای بزرگ‌ترِ ما:", mine[:3], "…")
print("همان چیزی که sorted می‌دهد؟", mine == sorted(pools[8_000], reverse=True)[:K])
```

```text
ده تای بزرگ‌ترِ ما: [999759, 999718, 999610] …
همان چیزی که sorted می‌دهد؟ True
```

```python
def k_cost(values, k):
    stats = [0]
    k_largest(values, k, stats)
    return stats[0]


print(f"— k = {K} ثابت، n دو برابر می‌شود")
table([(n, k_cost(pools[n], K)) for n in LADDER], "مقایسه", ",d")
print("\n— n = 8,000 ثابت، k دو برابر می‌شود")
print(f"{'k':>10}{'مقایسه':>18}{'نسبت به سطر قبل':>20}")
previous = None
for k in (10, 20, 40, 80):
    cost = k_cost(pools[8_000], k)
    ratio = "—" if not previous else f"{cost / previous:.2f}"
    print(f"{k:>10,}{cost:>18,}{ratio:>20}")
    previous = cost
```

```text
— k = 10 ثابت، n دو برابر می‌شود
         n            مقایسه     نسبت به سطر قبل
     1,000             1,216                   —
     2,000             2,299                1.89
     4,000             4,362                1.90
     8,000             8,395                1.92

— n = 8,000 ثابت، k دو برابر می‌شود
         k            مقایسه     نسبت به سطر قبل
        10             8,395                   —
        20             8,934                1.06
        40            10,220                1.14
        80            12,745                1.25
```

<div dir="rtl">

**دو جدول، دو پاسخِ متفاوت به دو سؤالِ متفاوت.**

جدولِ اول: با ثابت ماندنِ `k`، هزینه با `n` **خطی** است — نسبت‌ها `1.89`، `1.90`، `1.92`، از پایین به `2` نزدیک می‌شوند. (زیرِ `2` هستند چون کار دو بخش دارد: بخشِ **اجباری** که دقیقاً `n` است — یک مقایسه به‌ازای هر عضو — و بخشی که فقط وقتی خرج می‌شود که عددِ تازه از کوچک‌ترینِ `heap` بزرگ‌تر باشد. **هرچه جریان جلوتر می‌رود عبور از آن آستانه سخت‌تر می‌شود**، پس بخشِ دوم خیلی کندتر از `n` بالا می‌رود و جمعِ یک بخشِ خطی با یک بخشِ کندرشد، نسبتی کمی زیرِ `2` می‌دهد.)

جدولِ دوم مهم‌تر است: **با هشت برابر شدنِ `k`، هزینه فقط از `8,395` به `12,745` رفت — یک‌ونیم برابر.** یعنی `k` را می‌توانی بزرگ کنی بدونِ اینکه هزینه پابه‌پایش برود. **دلیلش هم در جدول است: `8,000` مقایسهٔ اول در هر سطر همان یک مقایسهٔ اجباری به‌ازای هر عضو است؛ هرچه بالای آن اضافه می‌شود مالِ جابه‌جایی‌های داخلِ `heap` است، که خیلی نادرتر اتفاق می‌افتند.**

## ۷. ساعت هم همان را می‌گوید؟ نه دقیقاً

شمارشِ مقایسه می‌گوید راهِ `heap` کارِ کمتری می‌کند. **ولی کارِ کمتر همیشه زمانِ کمتر نیست** — و ترمِ ۱ فصلِ ۹ دقیقاً همین را نشان داد.

</div>

```python
import heapq

huge = [rng.randrange(10 ** 6) for _ in range(200_000)]
by_sort = sorted(huge, reverse=True)[:K]
by_heapq = heapq.nlargest(K, huge)
by_hand = k_largest(huge, K, [0])
print("n =", f"{len(huge):,}", "· هر سه یک جواب می‌دهند؟", by_sort == by_heapq == by_hand)
print(f"sorted(...)[:k] : {1000 * clock(lambda: sorted(huge, reverse=True)[:K], repeat=3):7.1f} ms")
print(f"heapq.nlargest  : {1000 * clock(lambda: heapq.nlargest(K, huge), repeat=3):7.1f} ms")
print(f"heapِ دستیِ ما   : {1000 * clock(lambda: k_largest(huge, K, [0]), repeat=3):7.1f} ms")
```

```text-approx
n = 200,000 · هر سه یک جواب می‌دهند؟ True
sorted(...)[:k] :    35.1 ms
heapq.nlargest  :     2.9 ms
heapِ دستیِ ما   :    14.3 ms
```

<div dir="rtl">

**هر سه دقیقاً یک جواب می‌دهند و زمانشان یکی نیست.** عددهای تو فرق می‌کنند؛ چیزی که نباید خیلی فرق کند نسبت‌هاست: `heapq.nlargest` روی این ماشین حدودِ دوازده برابر از `sorted` سریع‌تر بود و حدودِ پنج برابر از نسخهٔ دستیِ ما.

**نسخهٔ ما از `sorted` جلو زد** — چون واقعاً کارِ کمتری می‌کند — **ولی از `heapq` عقب ماند، چون `heapq` همان الگوریتم است با کدی که پایتون نیست.** این همان درسِ ترمِ ۴ فصلِ ۸ است، این بار برای یک ساختارِ داده: **الگوریتم را برای فهمیدن خودت بنویس، و در کارِ واقعی از نسخهٔ کتابخانه استفاده کن.**

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک `heap` دستی با `sorted` و `heapq.nlargest`، روی همان دادهٔ یکسان و با خروجیِ برابرِ تأییدشده. **در کدام بازهٔ `n`؟** ۱٬۰۰۰ تا ۸٬۰۰۰ برای جدول‌های شمارش، و ۲۰۰٬۰۰۰ برای جدولِ زمان. **با چند تکرار، و کمینه یا میانگین؟** جدول‌های مقایسه یک اجرا، چون شمارش‌اند و قطعی؛ جدولِ زمان سه تکرار به‌علاوهٔ یک اجرای گرم‌کننده، کمینه.

> ✅ **چک کن:** در **هر دو** تابعِ `sift_up` و `sift_down`، علامتِ `<` را **فقط در مقایسهٔ مقدارها** (`h[i] < h[up]`، `h[left] < h[best]`، `h[right] < h[best]`) به `>` تبدیل کن — **به `left < n` و `right < n` دست نزن، آن‌ها مرزِ اندیس‌اند نه مقایسهٔ مقدار.** حالا بخشِ ۳ را دوباره بگیر. **ترتیبِ بیرون آمدن باید کاملاً برعکس شود — `[11, 9, 8, 6, 5, 3]` — و سطرِ مقایسه با `sorted` باید `False` بدهد.** این ساده‌ترین راهِ ساختنِ `heap` بیشینه است. اگر فقط یکی از دو تابع را عوض کنی، ساختار نه کمینه می‌ماند نه بیشینه می‌شود و خروجی‌اش بی‌معنا درمی‌آید — **که خودش نشان می‌دهد این دو تابع دو نیمهٔ یک قاعده‌اند، نه دو کارِ مستقل.**

> 🔧 **اگر کار نکرد:** `heap` روی عضوهایش `<` می‌زند. تا وقتی عددند مشکلی نیست، ولی `priority queue` واقعی معمولاً `tuple` نگه می‌دارد — اولویت، و خودِ کار. **و وقتی دو اولویت برابر شوند، پایتون سراغِ عضوِ دومِ `tuple` می‌رود:**

</div>

```python
try:
    jobs = []
    heapq.heappush(jobs, (2, {"name": "backup"}))
    heapq.heappush(jobs, (2, {"name": "report"}))
except TypeError as err:
    print(f"{type(err).__name__}: {err}")

jobs = []
for order_no, job in enumerate([(2, "backup"), (2, "report"), (1, "alert")]):
    heapq.heappush(jobs, (job[0], order_no, job[1]))
print("با شمارندهٔ ترتیب:", [heapq.heappop(jobs)[2] for _ in range(3)])
```

```text
TypeError: '<' not supported between instances of 'dict' and 'dict'
با شمارندهٔ ترتیب: ['alert', 'backup', 'report']
```

<div dir="rtl">

**بدترین خاصیتِ این خطا این است که تصادفی به‌نظر می‌رسد:** تا وقتی اولویت‌ها یکتا باشند هیچ اتفاقی نمی‌افتد، و اولین باری که دو کار اولویتِ یکسان بگیرند، برنامه می‌ایستد. راهِ حلِ استاندارد همان چیزی است که در سطرِ دوم می‌بینی: **یک شمارندهٔ ترتیب به‌عنوان عضوِ دوم**، که هم گره را باز می‌کند و هم کارهای هم‌اولویت را به‌ترتیبِ ورود بیرون می‌دهد.

> 🤖 **از دستیارت بپرس:** «چرا هزینهٔ `n` درج در `heap` خطی است ولی `n` درج به‌علاوهٔ `n` برداشت نیست؟» — جوابِ درست باید بگوید `sift_up` معمولاً زود متوقف می‌شود و `sift_down` معمولاً تا ته می‌رود. بعد **جدولِ دومِ بخشِ ۶ را جلویش بگذار و بپرس:** «چرا هشت برابر شدنِ `k` هزینه را هشت برابر نکرد؟»

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `heap` | هیپ | `list`ی که در آن هر پدر از فرزندانش کوچک‌تر است |
| heap property | هیپ پراپرتی | خاصیتِ `heap`: قیدی که فقط بینِ پدر و فرزند برقرار است |
| sift up | سیفت آپ | بالا بردنِ یک عضو تا جای درستش |
| sift down | سیفت داون | پایین آوردنِ یک عضو تا جای درستش |
| `priority queue` | پرایوریتی کیو | صفی که خروجی‌اش به اولویت است، نه به ترتیبِ ورود |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا خاصیتِ `heap` از مرتب‌بودن ضعیف‌تر است، و چرا همین ضعف ارزانش می‌کند؟

**تمرینِ اجباری:** تابعی بنویس که یک `list` را بگیرد و بگوید خاصیتِ `heap` را دارد یا نه، و اگر ندارد اولین خانهٔ خاطی را برگرداند. **حالا با آن، جدولِ بخشِ ۴ را دوباره بگیر و بعد از هر درج وارسی کن که خاصیت هنوز برقرار است.** سؤالِ اصلی: **این وارسی خودش چقدر خرج دارد؟** جدولِ چهار اندازه‌ای‌اش را بگیر و بگو نسبت به کارِ خودِ `heap` چه مرتبه‌ای دارد.

**تمرینِ ستاره‌دار ⭐:** به‌جای `heap` ده‌تایی، `k` بزرگ‌ترین را با یک `list` مرتبِ ده‌تایی پیدا کن (هر عضوِ تازه را با `insert` سرِ جایش بگذار و آخری را بینداز دور). **قبل از اجرا پیش‌بینی کن** کدام‌یک برای `k = 10` برنده می‌شود و کدام برای `k = 1000`، و **از کدام جدولِ ترمِ ۲ پیش‌بینی‌ات را درآورده‌ای**. حالا هر دو را برای هر دو `k` اندازه بگیر و خطای پیش‌بینی‌ات را بنویس.

## در فصل بعد

درخت یک قید دارد که تا حالا به آن دست نزده‌ایم: **هر گره فقط یک پدر دارد و هیچ حلقه‌ای وجود ندارد.** ولی خیلی از رابطه‌های واقعی این‌طور نیستند — دو شهر می‌توانند از دو راه به هم وصل باشند، و دو نفر می‌توانند دوستِ مشترک داشته باشند.

**فصلِ بعد آن قید را برمی‌دارد و به گراف می‌رسیم**، با دو نمایشِ کاملاً متفاوت که در یک گرافِ ۴٬۰۰۰ گره‌ای یکی `16,261,048` بایت می‌گیرد و دیگری `627,864` بایت — تا وقتی که چگالی از `0.107` بگذرد و ورق برگردد.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t5/s04-heap (یادستان, Yaadestan)
