AlgoVerse

هرم کمینه-بیشینه

هرمی که سطرهای زوجش هرم کمینه و سطرهای فردش هرم بیشینه‌اند؛ هم کمینه و هم بیشینه در O(1) پیدا و در O(log n) حذف می‌شوند (صف اولویت دوطرفه).

گاهی هم کمینه و هم بیشینه را لازم داریم (صف اولویت دوطرفه). هرم کمینه-بیشینه (Atkinson و همکاران) یک درخت دودویی کامل در آرایه است که سطرهایش یکی‌درمیان «کمینه» و «بیشینه» اند:

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

ده درج، بعد حذف کمینه (۰) و حذف بیشینه (−۱). ریشه کمینه است و بیشینه یکی از دو فرزند ریشه.

  1. def min_max_heap(ops):
  2. # A positive number is inserted, 0 deletes the minimum, a negative number deletes the maximum.
  3. heap = []
  4. removed = []
  5. for x in ops:
  6. if x > 0:
  7. heap.append(x)
  8. bubble_up(heap, len(heap) - 1)
  9. elif not heap:
  10. continue
  11. elif x == 0:
  12. removed.append(heap[0])
  13. remove_at(heap, 0)
  14. else:
  15. i = 0
  16. if len(heap) > 1:
  17. i = 1
  18. if len(heap) > 2 and heap[2] > heap[1]:
  19. i = 2
  20. removed.append(heap[i])
  21. remove_at(heap, i)
  22. return removed
  25. def on_min_level(i):
  26. # Levels 0, 2, 4, ... are min levels; the root is the minimum, its children hold the maximum.
  27. return (i + 1).bit_length() % 2 == 1
  30. def better(a, b, low):
  31. if low:
  32. return a < b
  33. return a > b
  36. def bubble_up(heap, i):
  37. if i == 0:
  38. return
  39. p = (i - 1) // 2
  40. low = on_min_level(i)
  41. if better(heap[p], heap[i], low):
  42. heap[i], heap[p] = heap[p], heap[i]
  43. i = p
  44. low = not low
  45. while i > 2:
  46. g = ((i - 1) // 2 - 1) // 2
  47. if not better(heap[i], heap[g], low):
  48. break
  49. heap[i], heap[g] = heap[g], heap[i]
  50. i = g
  53. def remove_at(heap, i):
  54. last = heap.pop()
  55. if i < len(heap):
  56. heap[i] = last
  57. trickle_down(heap, i)
  60. def trickle_down(heap, i):
  61. low = on_min_level(i)
  62. while 2 * i + 1 < len(heap):
  63. # m: the best of i's children and grandchildren (the smallest on a min level, the largest on a max level).
  64. m = 2 * i + 1
  65. for c in [2 * i + 1, 2 * i + 2, 4 * i + 3, 4 * i + 4, 4 * i + 5, 4 * i + 6]:
  66. if c < len(heap) and better(heap[c], heap[m], low):
  67. m = c
  68. if not better(heap[m], heap[i], low):
  69. return
  70. heap[i], heap[m] = heap[m], heap[i]
  71. if m <= 2 * i + 2:
  72. return
  73. p = (m - 1) // 2
  74. if better(heap[p], heap[m], low):
  75. heap[m], heap[p] = heap[p], heap[m]
  76. i = m

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

شروع اجرا

1270407309458015200-11207014027330495456807158209010-111

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

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

ops list

1270407309458015200-1

Call stack

  1. min_max_heap()خط 1
گام ۱ از ۳۱۵
خط سیاه = inserted, deleted_min, deleted_max · خط نارنجی = گام کلیدیinserted: 0/10 · swap_grandparent: 0/2 · swap_parent: 0/2 · last_moves: 0/2 · swap_down: 0/2 · deleted_min: 0/1 · deleted_max: 0/1
    توضیح

    ایده

    گاهی هم کمینه و هم بیشینه را لازم داریم (صف اولویت دوطرفه). هرم کمینه-بیشینه (Atkinson و همکاران) یک درخت دودویی کامل در آرایه است که سطرهایش یکی‌درمیان «کمینه» و «بیشینه» اند:

    • عضوی روی سطر کمینه (سطر ۰، ۲، …) از همه‌ی نوادگانش کوچک‌تر یا مساوی است؛
    • عضوی روی سطر بیشینه (سطر ۱، ۳، …) از همه‌ی نوادگانش بزرگ‌تر یا مساوی است.

    پس کمینه ریشه است و بیشینه بزرگ‌ترِ دو فرزند ریشه.

    درج

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

    حذف

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

    ورودی

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