LogoENEnglish

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

هیپ دودویی یکی از ظریف‌ترین ساختارهای داده در علوم کامپیوتر است، که هم یک الگوریتم مرتب‌سازی کارآمد درجا و هم انتزاع صف اولویت مورد استفاده در سراسر طراحی الگوریتم را ممکن می‌سازد. این راهنمای جامع ویژگی‌های هیپ و نمایش آرایه‌ای، عملیات اصلی heapify، ساخت یک هیپ از یک آرایه مرتب‌نشده، الگوریتم کامل heapsort، و عملیات‌های صف اولویت ساخته‌شده روی هیپ‌ها را پوشش می‌دهد.

صف اولویتهیپ دودوییالگوریتم Heapsort,

~7 دقیقه مطالعه · آخرین به‌روزرسانی ۱۶ شهریور ۱۴۰۵

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

یک 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) یک پیمایش خطی ساده در سراسر یک لیست مرتب‌نشده، اغلب این چیزی است که این الگوریتم‌های گراف را برای ورودی‌های بزرگ عملی می‌کند.

نوشته و پژوهش‌شده توسط دکتر شاهین صیامی

مقالات مرتبط

Quicksort: راهنمای کامل توصیف، کارایی، و تصادفی‌سازی

Quicksort یکی از پراستفاده‌ترین الگوریتم‌های مرتب‌سازی در عمل است، که به‌خاطر کارایی عالی حالت‌میانگین و عملیات درجا ارزشمند است، با وجود داشتن بدترین‌حالت نظری ضعیف. این راهنمای جامع الگوریتم مبتنی بر partition را با جزئیات پوشش می‌دهد، هم زمان اجرای بدترین‌حالت و هم مورد انتظار آن را تحلیل می‌کند، و توضیح می‌دهد تصادفی‌سازی چگونه آن را به یک الگوریتم به‌طور قابل‌اعتماد کارآمد صرف‌نظر از ترتیب ورودی تبدیل می‌کند.

ادامه

<h2>Why Randomness Enters Algorithm Analysis</h2> <p>The worst-case, best-case, and average-case running times discussed earlier in this series all assume the algorithm itself behaves deterministically, and any variation comes purely from the input. A different situation arises when either the input distribution is unknown or an algorithm deliberately makes random choices during its own execution. Both situations require the tools of <code>Probabilistic Analysis</code>.</p> <h2>The Hiring Problem: A Motivating Example</h2> <p>Consider a company interviewing candidates one at a time for a position, always hiring the current best candidate seen so far and firing the previous hire. Each interview costs a small amount, but each hire costs significantly more, since it involves paperwork, onboarding, and severance for the person being replaced. The question is: what is the expected total hiring cost across the entire process?</p> <pre class="code-block"><code>HIRE-ASSISTANT(n): best = candidate 0 (a placeholder, ranked worst) for i = 1 to n: interview candidate i if candidate i is better than best: best = candidate i hire candidate i</code></pre><br> <p>If candidates arrive in the worst possible order — already sorted from worst to best — every single candidate is hired, resulting in <code>n</code> hires, a costly worst case. But if the order of candidates is random, far fewer hires are expected on average, since a random arrival order makes it unlikely that many consecutive candidates each set a new record.</p> <h2>Two Approaches to Handling the Order of Inputs</h2> <p>There are two distinct ways to reason about this randomness, and it is important not to confuse them.</p> <ul> <li><code>Probabilistic Analysis of a Deterministic Algorithm</code>: assume the input itself comes from some probability distribution (such as a uniformly random ordering of candidates), and analyze the expected running time of a fixed, non-random algorithm over that input distribution.</li> <li><code>Randomized Algorithms</code>: the algorithm itself makes random choices during execution (such as randomly shuffling the candidate order before processing them, regardless of the order they actually arrived in), guaranteeing good expected performance for any input, since the randomness comes from the algorithm rather than an assumption about the input.</li> </ul> <p>The second approach is generally more powerful and reliable in practice, since it removes any dependence on assumptions about how inputs are distributed in the real world, which may not hold. A <code>Randomized Algorithm</code> for the hiring problem simply permutes the candidates randomly before running the same procedure, guaranteeing the same good expected cost regardless of the input's original order.</p> <h2>Indicator Random Variables: A Powerful Analytical Tool</h2> <p>Computing an expected value directly can be complicated when many interacting events are involved. <code>Indicator Random Variables</code> provide an elegant technique that dramatically simplifies such calculations, especially when combined with the linearity of expectation.</p> <p>For an event <code>A</code>, define the indicator random variable:</p> <pre class="code-block"><code>I{A} = 1 if A occurs I{A} = 0 if A does not occur Key property: E[I{A}] = Pr{A}</code></pre><br> <p>The expected value of an indicator variable simply equals the probability of the event it indicates. This becomes powerful when combined with <code>Linearity of Expectation</code>, which states that the expected value of a sum of random variables equals the sum of their expected values, regardless of whether the variables are independent.</p> <pre class="code-block"><code>E[X1 + X2 + ... + Xn] = E[X1] + E[X2] + ... + E[Xn] This holds even when the Xi are NOT independent — a crucial and often surprising fact</code></pre><br> <h2>Applying Indicator Variables to the Hiring Problem</h2> <p>Let <code>Xi</code> be the indicator random variable for the event that candidate <code>i</code> is hired. The total number of hires is <code>X = X1 + X2 + ... + Xn</code>. By linearity of expectation:</p> <pre class="code-block"><code>E[X] = E[X1] + E[X2] + ... + E[Xn] = Σ Pr{candidate i is hired}</code></pre><br> <p>Candidate <code>i</code> is hired precisely when candidate <code>i</code> is the best among the first <code>i</code> candidates seen so far. If the candidates arrive in a uniformly random order, candidate <code>i</code> is equally likely to be the best, second-best, or any rank among the first <code>i</code> candidates, so:</p> <pre class="code-block"><code>Pr{candidate i is hired} = 1/i Therefore: E[X] = Σ (i=1 to n) 1/i = H(n) This is the Harmonic Series, and H(n) = Θ(ln n)</code></pre><br> <p>This remarkable result shows that, despite there being <code>n</code> candidates, the expected number of hires grows only logarithmically with <code>n</code>, a dramatic improvement over the worst-case scenario of <code>n</code> hires. This calculation, made simple through indicator variables, would be considerably more complex using direct probability calculations involving joint distributions.</p> <h2>Why This Technique Generalizes So Widely</h2> <p>The indicator random variable technique is not specific to the hiring problem; it is a general tool applicable whenever a quantity of interest can be expressed as a sum of simpler zero-or-one outcomes, even when those outcomes are correlated with each other. This makes it one of the most broadly useful techniques in the probabilistic analysis of algorithms, and it reappears throughout later topics in this series wherever expected running time needs to be computed.</p> <h2>Why Randomization Matters for Real-World Algorithm Design</h2> <p>Randomized algorithms are used throughout computer science specifically because they can guarantee good expected performance without needing any assumption about the distribution of real-world inputs, protecting against adversarial or unusually structured inputs that could otherwise trigger an algorithm's worst case. A prominent example, explored in depth later in this series, is randomized quicksort, where randomly shuffling the input before sorting protects against the specific input orderings that would otherwise trigger quicksort's quadratic worst case.</p>

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

ادامه

حل رابطه‌های بازگشتی: Substitution، Recursion-Tree، و روش استاد

زمان اجرای هر الگوریتم تقسیم‌و‌غلبه توسط یک رابطه بازگشتی توصیف می‌شود، و حل آن رابطه برای درک کارایی الگوریتم ضروری است. این راهنمای جامع سه تکنیک استاندارد برای حل رابطه‌های بازگشتی را پوشش می‌دهد: روش substitution برای اثبات یک کران حدس‌زده‌شده، روش recursion-tree برای تولید یک حدس، و روش استاد به‌عنوان یک میان‌بر سریع برای یک دسته رایج از رابطه‌های بازگشتی.

ادامه

تقسیم‌و‌غلبه برای ضرب ماتریس: از رویکرد ساده تا الگوریتم اشتراسن

ضرب دو ماتریس یک عملیات بنیادین در علوم کامپیوتر است، و رویکرد ساده بسیار دور از بهینه است. این راهنمای جامع الگوریتم استاندارد ضرب ماتریس با زمان مکعبی را توضیح می‌دهد، نشان می‌دهد چگونه یک رویکرد تقسیم‌و‌غلبه ساده در بهبود آن شکست می‌خورد، و الگوریتم قابل‌توجه اشتراسن که به یک زمان اجرای مجانبی واقعاً سریع‌تر می‌رسد را مرور می‌کند.

ادامه

نمادگذاری مجانبی: راهنمای کامل O، Ω، و Θ

مقایسه منصفانه الگوریتم‌ها نیازمند یک زبان ریاضی است که فاکتورهای ثابت را نادیده بگیرد و روی نرخ رشد با بزرگ‌شدن اندازه ورودی تمرکز کند. این راهنمای جامع تعاریف رسمی نمادگذاری Big-O، Big-Omega، و Big-Theta را پوشش می‌دهد، توضیح می‌دهد چگونه کران‌های مجانبی را مستقیماً از تعاریف‌شان اثبات کنیم، و توابع و نرخ‌های رشد استانداردی که هر تحلیل الگوریتمی به آن‌ها متکی است را مرور می‌کند.

ادامه

الگوریتم چیست و چگونه تحلیل می‌شود: راهنمای کامل شروع

پیش از پرداختن به الگوریتم‌های خاص، ضروری است درک کنیم یک الگوریتم واقعاً چیست، چرا مطالعه الگوریتم‌ها حتی با سخت‌افزار سریع امروزی اهمیت دارد، و چگونه کارایی یک الگوریتم را به‌طور دقیق تحلیل کنیم. این راهنمای جامع تعریف رسمی الگوریتم را پوشش می‌دهد، insertion sort را به‌عنوان اولین مثال کامل مرور می‌کند، و تکنیک‌های اصلی برای سنجش و مقایسه زمان اجرا را معرفی می‌کند.

ادامه
مقاله‌ی قبلیمقاله‌ی بعدی