مرتب‌سازی هرمی

تبدیل و حل

آرایه را به یک هرم بیشینه تبدیل می‌کند و بعد بارها بزرگ‌ترین عضو را از ریشه برمی‌دارد و به انتهای آرایه می‌برد.

هرم بیشینه درخت دودویی کاملی است که هر گره از فرزندانش کوچک‌تر نیست، پس بزرگ‌ترین عضو همیشه در ریشه است. این درخت را می‌شود بدون اشاره‌گر در خود آرایه نگه داشت: فرزندان خانه‌ی i در 2i + 1 و 2i + 2 هستند.

ادامه‌ی توضیح ↓

زمان: O(n log n)
حافظه: O(1)
CLRS، بخش ۶.۴
هوروویتز–ساهنی، فصل ۷

ورودی:

n=10خروجی PDF

ده عدد درهم؛ اول هرم ساخته می‌شود، بعد عضوها یکی‌یکی از ریشه برداشته می‌شوند.

def heap_sort(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1):
sift_down(a, i, n)
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift_down(a, 0, end)
return a
def sift_down(a, i, size):
while True:
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < size:
if a[left] > a[largest]:
largest = left
if right < size:
if a[right] > a[largest]:
largest = right
if largest == i:
return
a[i], a[largest] = a[largest], a[i]
i = largest

ناوردا: در مرحله‌ی دوم، a[0..end−1] یک هرم بیشینه است و a[end..n−1] بزرگ‌ترین عضوها را مرتب‌شده دارد.

شروع اجرا

متغیرهای محلی

نارنجی = در همین گام عوض شد

`a` list

4132169101487

Call stack

heap_sort()خط 1

گام ۱ از ۴۲۷

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

comparisons
swaps
ورودی فعلی (n=10)

نمایش به شکل جدول

n	comparisons	swaps
4	6.4	2.8
6	15.2	7
8	26.3	12
10	39.8	18.1
12	52.3	24.8
14	63.5	28.3

توضیح

ایده

مرتب‌سازی هرمی دو مرحله دارد:

ساخت هرم: از آخرین گره‌ی غیربرگ به سمت ریشه، روی هر گره sift_down را اجرا کن تا آرایه هرم بیشینه شود.
برداشتن از ریشه: ریشه (بزرگ‌ترین عضو) را با آخرین خانه‌ی هرم جابه‌جا کن، اندازه‌ی هرم را یکی کم کن و ریشه‌ی تازه را با sift_down پایین ببر. تا وقتی هرم یک عضو دارد، تکرار کن.

sift_down

گره را با بزرگ‌ترین فرزندش مقایسه کن. اگر فرزند بزرگ‌تر بود، جابه‌جا کن و از جای تازه ادامه بده؛ وگرنه کار تمام است. چون ارتفاع هرم log n است، هر sift_down حداکثر O(log n) کار دارد.

هزینه

ساخت هرم O(n) است و مرحله‌ی دوم n − 1 بار sift_down اجرا می‌کند، پس زمان در همه‌ی حالت‌ها O(n log n) است.
مرتب‌سازی درجا انجام می‌شود: حافظه‌ی اضافه O(1).
مرتب‌سازی هرمی پایدار نیست: جابه‌جایی‌های دور ممکن است ترتیب عضوهای برابر را عوض کنند.

در trace به چه چیزی نگاه کنی

بالای میله‌ها همان آرایه به شکل درخت هرم کشیده شده است. فقط خانه‌هایی که هنوز در هرم‌اند در درخت دیده می‌شوند.
میله‌های سیاه بخش مرتب‌شده‌ی انتهای آرایه‌اند که هر دور یکی بزرگ‌تر می‌شود.
با سطح جزئیات «هر دور حلقه» فقط برداشتن‌ها را از ریشه ببین.