Heapsort و صف‌های اولویت: راهنمای کامل هیپ دودویی

هیپ دودویی چیست

یک Binary Heap (هیپ دودویی) یک درخت دودویی تقریباً کامل است که یک ویژگی ترتیبی خاص را برآورده می‌کند، و معمولاً به‌طور ضمنی در یک آرایه ذخیره می‌شود نه با استفاده از گره‌های درخت مبتنی بر اشاره‌گر صریح. دو نوع وجود دارد: یک Max-Heap، جایی که مقدار هر گره والد بزرگ‌تر یا مساوی مقادیر فرزندانش است، و یک Min-Heap، جایی که عکس آن برقرار است. این مقاله روی max-heap ها تمرکز می‌کند، چون پایه heapsort هستند، هرچند هر عملیاتی معادل مستقیم min-heap هم دارد.

نمایش یک هیپ در یک آرایه

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

برای یک گره در ایندکس i (با استفاده از ایندکس‌گذاری مبتنی‌بر-1):
PARENT(i) = ⌊i / 2⌋
LEFT(i)   = 2i
RIGHT(i)  = 2i + 1

مثال هیپ: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
ایندکس:      1   2   3  4  5  6  7  8  9  10

این نمایانگر درخت زیر است:
                16
              /    \
            14      10
           /  \     /  \
          8    7   9    3
         / \   |
        2   4  1

Max-Heap Property (ویژگی max-heap) نیازمند این است که برای هر گره i غیر از ریشه، A[PARENT(i)] ≥ A[i] برقرار باشد. توجه کنید این ویژگی فقط روابط والد-فرزند را محدود می‌کند؛ چیزی درباره ترتیب نسبی خواهر-برادرها یا گره‌ها در زیردرخت‌های مختلف نمی‌گوید، به همین دلیل یک هیپ یک ساختار کاملاً مرتب‌شده نیست.

عملیات اصلی: MAX-HEAPIFY

MAX-HEAPIFY عملیات بنیادینی است که ویژگی max-heap را حفظ می‌کند. فرض می‌کند درخت‌های دودویی ریشه‌دار در فرزندان چپ و راست یک گره از قبل max-heap های معتبری هستند، اما خود گره ممکن است ویژگی را با کوچک‌تر بودن از یکی از فرزندانش نقض کند. این را با "غربال کردن به‌سمت پایین" مقدار ناقض حل می‌کند.

MAX-HEAPIFY(A, i, n):
  l = LEFT(i)
  r = RIGHT(i)
  اگر l ≤ n و A[l] > A[i]:
      largest = l
  در غیر این صورت:
      largest = i
  اگر r ≤ n و A[r] > A[largest]:
      largest = r
  اگر largest ≠ i:
      A[i] را با A[largest] جابه‌جا کن
      MAX-HEAPIFY(A, largest, n)

این الگوریتم گره را با هر دو فرزندش مقایسه می‌کند، بزرگ‌ترین از میان سه را شناسایی می‌کند، و اگر یک فرزند از گره بزرگ‌تر باشد، آن‌ها را جابه‌جا می‌کند و به‌طور بازگشتی ادامه می‌دهد تا ویژگی هیپ را در پایین‌تر درخت اصلاح کند. از آنجا که یک هیپ ارتفاع Θ(log n) دارد، و MAX-HEAPIFY کار ثابتی در هر سطح که پایین می‌رود انجام می‌دهد، زمان اجرای آن O(log n) است.

ساخت یک هیپ از یک آرایه مرتب‌نشده

با داشتن یک آرایه دلخواه، BUILD-MAX-HEAP آن را با فراخوانی MAX-HEAPIFY روی هر گره غیربرگ، کار از آخرین گره غیربرگ تا ریشه، به یک max-heap معتبر تبدیل می‌کند.

BUILD-MAX-HEAP(A, n):
  برای i = ⌊n/2⌋ کاهشی تا 1:
      MAX-HEAPIFY(A, i, n)

دلیل شروع از ⌊n/2⌋ به‌جای اولین عنصر این است که همه ایندکس‌های آرایه بزرگ‌تر از ⌊n/2⌋ برگ‌اند، که به‌طور بدیهی هیپ‌های یک‌گره‌ای معتبر بدون نیاز به کار هستند.

یک نتیجه شگفت‌انگیز: BUILD-MAX-HEAP در زمان خطی اجرا می‌شود

یک تحلیل ساده ممکن است پیشنهاد کند از آنجا که تقریباً n/2 فراخوانی به MAX-HEAPIFY وجود دارد، هرکدام هزینه O(log n)، هزینه کل O(n log n) است. این کران درست است اما محکم نیست. یک تحلیل دقیق‌تر آشکار می‌کند بیشتر گره‌ها نزدیک ته درخت هستند، جایی که MAX-HEAPIFY کار بسیار کمی انجام می‌دهد، چون بیشتر زیردرخت‌ها کوتاه‌اند.

در ارتفاع h، حداکثر ⌈n/2^(h+1)⌉ گره وجود دارد،
و MAX-HEAPIFY روی یک گره با ارتفاع h هزینه O(h) دارد

هزینه کل = Σ (h=0 تا ⌊log n⌋) ⌈n/2^(h+1)⌉ · O(h)
           = O(n · Σ (h=0 تا ∞) h/2^h)

با استفاده از نتیجه شناخته‌شده Σ (h=0 تا ∞) h·xʰ = x/(1-x)²
با x = 1/2، این مجموع به یک ثابت ارزیابی می‌شود

بنابراین، هزینه کل = O(n)

این ثابت می‌کند BUILD-MAX-HEAP در زمان Θ(n) اجرا می‌شود، یک الگوریتم زمان-خطی — به‌طور قابل‌توجهی بهتر از کران شل O(n log n) که یک تحلیل ساده پیشنهاد می‌کند. این یک مثال کلاسیک از این است که چرا تحلیل دقیق و محکم بسیار بیشتر از یک تخمین سریع و شل اهمیت دارد.

الگوریتم کامل Heapsort

Heapsort رویه ساخت هیپ را با یک فرآیند استخراج تکراری ترکیب می‌کند تا یک آرایه را درجا مرتب کند.

HEAPSORT(A, n):
  BUILD-MAX-HEAP(A, n)
  برای i = n کاهشی تا 2:
      A[1] را با A[i] جابه‌جا کن
      n = n - 1  (هیپ را کوچک کن، پسوند مرتب‌شده را حذف کن)
      MAX-HEAPIFY(A, 1, n)

الگوریتم با استخراج مکرر عنصر حداکثر (همیشه در ریشه، ایندکس ۱) و قرار دادن آن در انتهای ناحیه فعلاً مرتب‌نشده کار می‌کند، سپس ویژگی هیپ را روی هیپ اکنون کوچک‌تر بازیابی می‌کند. هرکدام از این n-1 گام استخراج هزینه O(log n) برای فراخوانی MAX-HEAPIFY دارد، که زمان اجرای کل Θ(n log n) برای مرحله مرتب‌سازی می‌دهد، به‌علاوه Θ(n) برای ساخت اولیه، برای زمان اجرای کلی Θ(n log n).

Heapsort یک مزیت عملی مهم نسبت به merge sort دارد، الگوریتم Θ(n log n) دیگری که بعداً در این مجموعه پوشش داده می‌شود: به‌صورت In Place (درجا) مرتب می‌کند، و فقط نیازمند مقدار ثابتی حافظه فراتر از خود آرایه ورودی است، در حالی که merge sort نیازمند Θ(n) حافظه اضافی است.

صف‌های اولویت: کاربرد عملی هیپ‌ها

فراتر از مرتب‌سازی، اهمیت دنیای واقعی هیپ از استفاده‌اش به‌عنوان ساختار داده زیربنایی برای یک Priority Queue (صف اولویت) می‌آید، یک نوع داده انتزاعی که یک مجموعه از عناصر را نگه می‌دارد، هرکدام با یک اولویت مرتبط، و به‌طور کارآمد بازیابی و حذف عنصر با بالاترین اولویت را پشتیبانی می‌کند.

عملیات‌های اصلی صف اولویت، با استفاده از یک max-heap:

MAX-HEAP-MAXIMUM(A):        A[1] را برگردان         — O(1)
MAX-HEAP-EXTRACT-MAX(A, n): حداکثر را حذف و برگردان  — O(log n)
MAX-HEAP-INCREASE-KEY(A, i, key): مقدار یک کلید را بالا ببر  — O(log n)
MAX-HEAP-INSERT(A, key, n): یک عنصر جدید اضافه کن     — O(log n)

MAX-HEAP-EXTRACT-MAX ریشه را حذف می‌کند، آخرین عنصر را به موقعیت ریشه منتقل می‌کند، اندازه هیپ را کوچک می‌کند، و MAX-HEAPIFY را برای بازیابی ویژگی فراخوانی می‌کند. MAX-HEAP-INCREASE-KEY اولویت یک عنصر را بالا می‌برد و سپس آن را با جابه‌جایی مکرر با والدش تا بازیابی ویژگی هیپ، به‌سمت ریشه "حباب" می‌کند. MAX-HEAP-INSERT یک عنصر جدید را در ته هیپ با یک مقدار اولیه حداقلی اضافه می‌کند، سپس increase-key را برای بالا بردن آن به اولویت واقعی‌اش و حباب کردن آن به موقعیتش فراخوانی می‌کند.

چرا صف‌های اولویت در سراسر طراحی الگوریتم اهمیت دارند

صف‌های اولویت ساخته‌شده روی هیپ‌ها یک بلوک سازنده بنیادین هستند که در سراسر باقی این مجموعه استفاده می‌شوند، به‌ویژه در الگوریتم دیجکسترا برای کوتاه‌ترین مسیرها و الگوریتم پریم برای درخت پوشای کمینه، هر دو که بعداً در این مجموعه پوشش داده می‌شوند، جایی که انتخاب کارآمد "بهترین بعدی" عنصر در هر گام برای درستی و کارایی الگوریتم مرکزی است. هزینه O(log n) عملیات‌های هیپ، به‌جای هزینه O(n) یک پیمایش خطی ساده در سراسر یک لیست مرتب‌نشده، اغلب این چیزی است که این الگوریتم‌های گراف را برای ورودی‌های بزرگ عملی می‌کند.