AlgoVerse

صف اولویت با هرم

درج در هرم بیشینه با بالا بردن عضو تازه، و برداشتن بیشینه با پایین بردن عضوی که جای ریشه نشسته؛ هر دو O(log n).

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

ادامه‌ی توضیح ↓
ورودی:
n=10 · target=15خروجی PDF

هرم ده‌عضوی؛ کلید ۱۵ تا یک سطح زیر ریشه بالا می‌رود، بعد بیشینه (۱۶) برداشته می‌شود.

  1. def priority_queue(heap, key):
  2. insert(heap, key)
  3. top = extract_max(heap)
  4. return top, heap
  7. def insert(heap, key):
  8. heap.append(key)
  9. i = len(heap) - 1
  10. while i > 0:
  11. parent = (i - 1) // 2
  12. if heap[parent] >= heap[i]:
  13. break
  14. heap[i], heap[parent] = heap[parent], heap[i]
  15. i = parent
  18. def extract_max(heap):
  19. top = heap[0]
  20. heap[0] = heap[-1]
  21. heap.pop()
  22. i = 0
  23. size = len(heap)
  24. while True:
  25. largest = i
  26. left = 2 * i + 1
  27. right = 2 * i + 2
  28. if left < size:
  29. if heap[left] > heap[largest]:
  30. largest = left
  31. if right < size:
  32. if heap[right] > heap[largest]:
  33. largest = right
  34. if largest == i:
  35. return top
  36. heap[i], heap[largest] = heap[largest], heap[i]
  37. i = largest

ناوردا: به‌جز در یک جای در حال تعمیر، هیچ گره‌ای از والدش بزرگ‌تر نیست.

شروع اجرا

1614108793241target 1516014110283749536274819

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

key15

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

heap list

1614108793241

Call stack

  1. priority_queue()خط 1
گام ۱ از ۶۱
خط سیاه = inserted, extracted · خط نارنجی = گام کلیدیcompare: 0/8 · swap: 0/4 · append: 0/1 · inserted: 0/1 · move_last: 0/1 · extracted: 0/1

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

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

    • comparisons
    • swaps
    • ورودی فعلی (n=10)
    02468468101214n = تعداد عضوهای آرایهcomparisonsswaps
    نمایش به شکل جدول
    ncomparisonsswaps
    43.80.9
    65.21.8
    86.12.2
    107.22.8
    127.63.3
    147.33.3
    توضیح

    ایده

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

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

    هزینه

    ارتفاع هرم ⌊log n⌋ است و هر عمل حداکثر یک مسیر از ریشه تا برگ را طی می‌کند: O(log n). این همان صفی است که Dijkstra و Prim و زمان‌بندی کارها از آن استفاده می‌کنند.

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

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