در این فصل چه یاد میگیری#
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 بگذرد و ورق برگردد.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.