AlgoVerse

هرم دوجمله‌ای

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

درخت دوجمله‌ای درجه‌ی k، یعنی B_k، از دو B_{k−1} ساخته می‌شود که ریشه‌ی یکی فرزند ریشه‌ی دیگری شده است. پس 2^k گره دارد و ریشه‌اش k فرزند دارد.

ادامه‌ی توضیح ↓
ورودی:
n=8خروجی PDF

هفت درج: ۷ = ۱۱۱ در دودویی، پس سه درخت با ۱، ۲ و ۴ گره می‌ماند. بعد حذف کمینه.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.degree = 0
  5. self.children = [] # in increasing degree
  8. def binomial_heap(ops):
  9. heap = [] # the root list, in increasing degree
  10. removed = []
  11. for x in ops:
  12. if x > 0:
  13. union(heap, [Node(x)])
  14. elif not heap:
  15. continue
  16. else:
  17. m = heap[0]
  18. for r in heap:
  19. if r.key < m.key:
  20. m = r
  21. heap.remove(m)
  22. removed.append(m.key)
  23. union(heap, m.children)
  24. return removed
  27. def union(heap, other):
  28. # Merge the two root lists by degree, then link trees of equal degree, like adding binary numbers.
  29. heap.extend(other)
  30. heap.sort(key=lambda t: t.degree)
  31. i = 0
  32. while i < len(heap) - 1:
  33. x = heap[i]
  34. nx = heap[i + 1]
  35. if x.degree != nx.degree:
  36. i = i + 1
  37. elif i + 2 < len(heap) and heap[i + 2].degree == x.degree:
  38. i = i + 1
  39. elif x.key <= nx.key:
  40. link(nx, x)
  41. heap.pop(i + 1)
  42. else:
  43. link(x, nx)
  44. heap.pop(i)
  47. def link(y, z):
  48. # Two trees of degree k become one of degree k + 1: y goes under z.
  49. z.children.append(y)
  50. z.degree = z.degree + 1

ناوردا: هر درخت مرتب‌هرمی است، درخت درجه‌ی k دقیقاً 2^k گره دارد، و بعد از هر ادغام هیچ دو ریشه‌ای هم‌درجه نیستند.

شروع اجرا

∅

removed—

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

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

ops list

12725152833410

Call stack

  1. binomial_heap()خط 8
گام ۱ از ۲۰۷
خط سیاه = inserted, extracted · خط نارنجی = گام کلیدیmerged: 0/8 · inserted: 0/7 · link: 0/6 · min_root: 0/1 · three_alike: 0/1 · extracted: 0/1
    توضیح

    درخت دوجمله‌ای

    درخت دوجمله‌ای درجه‌ی k، یعنی B_k، از دو B_{k−1} ساخته می‌شود که ریشه‌ی یکی فرزند ریشه‌ی دیگری شده است. پس 2^k گره دارد و ریشه‌اش k فرزند دارد.

    هرم دوجمله‌ای

    مجموعه‌ای از درخت‌های دوجمله‌ای مرتب‌هرمی، حداکثر یکی از هر درجه. درخت‌هایی که هستند دقیقاً ارقام 1 نمایش دودویی n اند؛ پس حداکثر ⌊log n⌋ + 1 درخت داریم.

    ادغام = جمع دودویی

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

    • درج: ادغام با هرمی یک‌گره‌ای.
    • حذف کمینه: کمینه یکی از ریشه‌هاست؛ آن را برمی‌داریم و فرزندانش (که خودشان یک هرم دوجمله‌ای‌اند) را دوباره ادغام می‌کنیم.

    ورودی

    عدد مثبت درج می‌شود و 0 یعنی حذف کمینه.