بنیاد — ساختمان داده و الگوریتم، با اندازه‌گیری واقعی

فصل ۴ از ۸

پیشرفت ترم
۰٪

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

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

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

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

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

یک ردیف خانهٔ شماره‌دار در کنارِ درختی که هر گره‌اش دقیقاً به یکی از همان خانه‌ها وصل شده است

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

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

قبل از شروع#

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

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

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

📓 نوت‌بوک: نوت‌بوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

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

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

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)))
خانهٔ 0: مقدار  3  ·  فرزندان [5, 8]
خانهٔ 1: مقدار  5  ·  فرزندان [9, 6]
خانهٔ 2: مقدار  8  ·  فرزندان [11]
خانهٔ 3: مقدار  9  ·  فرزندان []
خانهٔ 4: مقدار  6  ·  فرزندان []
خانهٔ 5: مقدار 11  ·  فرزندان []

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

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

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

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

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

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

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

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

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

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]))
ترتیبِ بیرون آمدن: [3, 5, 6, 8, 9, 11]
همان چیزی است که sorted می‌دهد؟ True

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

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

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

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")
سه عددِ اول: [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

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

جدولِ اول 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ِ کمینه بدترین است و چرا.

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")
— 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

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

  • صعودی: دقیقاً 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 را هشت برابر کنیم، هزینه چند برابر می‌شود؟ هر دو را بنویس، بعد جدول‌ها را ببین.

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])
ده تای بزرگ‌ترِ ما: [999759, 999718, 999610] …
همان چیزی که sorted می‌دهد؟ True
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
— 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

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

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

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

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

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

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")
n = 200,000 · هر سه یک جواب می‌دهند؟ True
sorted(...)[:k] :    35.1 ms
heapq.nlargest  :     2.9 ms
heapِ دستیِ ما   :    14.3 ms

هر سه دقیقاً یک جواب می‌دهند و زمانشان یکی نیست. عددهای تو فرق می‌کنند؛ چیزی که نباید خیلی فرق کند نسبت‌هاست: 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 می‌رود:

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)])
TypeError: '<' not supported between instances of 'dict' and 'dict'
با شمارندهٔ ترتیب: ['alert', 'backup', 'report']

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

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

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

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

تمرین‌ها

اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.

در فصل بعد#

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

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

به آخر این فصل رسیدی!

اگر ساختی و جواب داد، این دکمه مال توست.