AlgoVerse

هرم چپ‌گرا (Leftist)

هرمی که دو هرم را در O(log n) ادغام می‌کند: همه‌ی کار روی ستون راست کوتاه انجام می‌شود و هر جا سمت چپ کوتاه‌تر شد، دو فرزند جابه‌جا می‌شوند. درج و حذف کمینه هم همان ادغام‌اند.

هرم دودویی آرایه‌ای درج و حذف کمینه را خوب انجام می‌دهد، ولی ادغام دو هرم در آن O(n) است. هرم چپ‌گرا (Crane) ادغام را در O(log n) انجام می‌دهد، و درج و حذف کمینه را هم با ادغام می‌سازد.

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

هفت درج و بعد دو حذف کمینه؛ عدد کوچک زیر هر گره s آن است و هر جا s چپ کمتر شد، فرزندان جابه‌جا می‌شوند.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  6. self.s = 1 # the length of the shortest path down to an empty spot
  9. def leftist_heap(ops):
  10. root = None
  11. removed = []
  12. for x in ops:
  13. if x > 0:
  14. root = merge(root, Node(x))
  15. elif root is None:
  16. continue
  17. else:
  18. removed.append(root.key)
  19. root = merge(root.left, root.right)
  20. return removed
  23. def s(x):
  24. if x is None:
  25. return 0
  26. return x.s
  29. def merge(a, b):
  30. # Merge along the right spines, which are short (O(log n)), and swap children where the left side gets too short.
  31. if a is None:
  32. return b
  33. if b is None:
  34. return a
  35. if b.key < a.key:
  36. a, b = b, a
  37. a.right = merge(a.right, b)
  38. if s(a.left) < s(a.right):
  39. a.left, a.right = a.right, a.left
  40. a.s = s(a.right) + 1
  41. return a

ناوردا: هر گره از فرزندانش کوچک‌تر یا مساوی است، و s فرزند چپ هیچ‌وقت از s فرزند راست کمتر نیست.

شروع اجرا

∅

removed—

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

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

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

ops list

592738100

Call stack

  1. leftist_heap()خط 9
گام ۱ از ۲۷۹
خط سیاه = inserted, deleted_min · خط نارنجی = گام کلیدیinserted: 0/7 · merged_right: 0/10 · swap_children: 0/6 · smaller_root: 0/4 · deleted_min: 0/2
    توضیح

    چرا ادغام

    هرم دودویی آرایه‌ای درج و حذف کمینه را خوب انجام می‌دهد، ولی ادغام دو هرم در آن O(n) است. هرم چپ‌گرا (Crane) ادغام را در O(log n) انجام می‌دهد، و درج و حذف کمینه را هم با ادغام می‌سازد.

    s و چپ‌گرایی

    برای هر گره، s طول کوتاه‌ترین مسیر تا یک جای خالی است. درخت چپ‌گرا است اگر برای هر گره s(چپ) ≥ s(راست). پس ستون راست (از ریشه همیشه به راست) کوتاه‌ترین مسیر است و طولش حداکثر log₂(n + 1) است.

    ادغام

    ریشه‌ی کوچک‌تر ریشه‌ی جواب است؛ زیردرخت راستش را به صورت بازگشتی با هرم دیگر ادغام می‌کنیم. در برگشت، اگر s چپ کمتر از راست شد، دو فرزند را جابه‌جا می‌کنیم. همه‌ی کار روی دو ستون راست است: O(log n).

    ورودی

    عدد مثبت درج می‌شود و 0 یعنی حذف کمینه. عدد کوچک زیر هر گره s آن است.