درخت مسابقه

• ایجاد درخت: ${\displaystyle O(n)}$
  

رئوس خارجی نماینده عناصر می‌شوند و سپس هر راس داخلی برنده بین دو فرزند خود را ذخیره کرده و به این ترتیب تا ریشه پیش می‌رویم. در نهایت ریشه حاوی برندهٔ نهایی (عنصر کمینه یا بیشینه) بین تمام عناصر خواهد بود. به دلیل اینکه تعداد کل رئوس ضریبی از تعداد عناصر می‌شود، در نتیجه زمان ایجاد درخت از ${\displaystyle O(n)}$ است.

• حذف عنصر کمینه (بیشینه): ${\displaystyle O(\log n)}$
  

زمانی که بخواهیم عنصر کمینه (بیشینه) را حذف کنیم، مقدار آن را مثبت بی‌نهایت (منفی بی‌نهایت) می‌کنیم و سپس تک‌مسابقاتی که روی مسیر بین آن عنصر و ریشه وجود دارد را دوباره انجام می‌دهیم تا درخت جدید ساخته شود. چون ارتفاع درخت از ${\displaystyle O(\log n)}$ است زمان حذف از ${\displaystyle O(\log n)}$ می‌شود.

• جایگزینی عنصر کمینه (بیشینه): ${\displaystyle O(\log n)}$
  

زمانی که بخواهیم عنصر کمینه (بیشینه) را جایگزین کنیم، مقدار جدید را به آن می‌دهیم و سپس تک‌مسابقاتی که روی مسیر بین آن عنصر و ریشه وجود دارد را دوباره انجام می‌دهیم تا درخت جدید ساخته شود. چون ارتفاع درخت از ${\displaystyle O(\log n)}$ است زمان جایگزینی نیز از ${\displaystyle O(\log n)}$ می‌شود.

در ادامه پیاده‌سازی درخت برنده با استفاده از آرایه به زبان پایتون آمده است.

import math
def build(A, B, x, l, r):
    if l == r:
        B[x] = (A[l], x)
    else:
        mid = (l + r) // 2
        build(A, B, 2 * x, l, mid)
        build(A, B, (2 * x) + 1, mid + 1, r)
        if B[(2 * x) + 1][0] < B[2 * x][0]:
            B[x] = B[(2 * x) + 1]
        else:
            B[x] = B[2 * x]

def pop(B):
    result = B[1][0]
    index = B[1][1]
    B[index] = None
    while index > 1:
        index = index // 2
        if B[index * 2] is None:
            minimum = B[(index * 2) + 1]
        elif B[(index * 2) + 1] is None:
            minimum = B[index * 2]
        else:
            minimum = min(B[index * 2], B[(index * 2) + 1])
        if minimum == B[index]:
            break
        B[index] = minimum
    return result

def minimum(B):
    return B[1][0]

def replace_minimum(B, value):
    result = B[1][0]
    index = B[1][1]
    B[index] = (value, index)
    while index > 1:
        index = index // 2
        if B[index * 2] is None:
            minimum = B[(index * 2) + 1]
        elif B[(index * 2) + 1] is None:
            minimum = B[index * 2]
        else:
            minimum = min(B[index * 2], B[(index * 2) + 1])
        if minimum == B[index]:
            break
        B[index] = minimum
    return result

A = [-8, 3, 17, 57, 0, -19, 21, 5, 965 , 2, 0, 1, 34, 83]
n = len(A)
B = [None] * (2 ** (math.ceil(math.log2(n)) + 1))
build(A, B, 1, 0, n - 1)
print(replace_minimum(B, -7))
print(pop(B))
print(minimum(B))

• ایجاد درخت: ${\displaystyle O(n)}$
  

رئوس خارجی نماینده عناصر می‌شوند و مقدار خود را به پدر به عنوان نتیجه می‌دهند. سپس هر راس داخلی بازنده عناصر داده شده توسط دو فرزند خود را ذخیره کرده و برنده آن‌ها را به عنوان نتیجه به راس پدر خود می‌دهد. به این ترتیب تا ریشه پیش می‌رویم. در نهایت ریشه حاوی بازندهٔ تک‌مسابقهٔ نهایی خواهد بود و برنده نهایی (عنصر کمینه یا بیشینه) بین تمام عناصر را به عنوان نتیجه به راسی جداگانه می‌دهد. به دلیل اینکه تعداد کل رئوس ضریبی از تعداد عناصر می‌شود، در نتیجه زمان ایجاد درخت از ${\displaystyle O(n)}$ است.

• حذف عنصر کمینه (بیشینه): ${\displaystyle O(\log n)}$
  

زمانی که بخواهیم عنصر کمینه (بیشینه) را حذف کنیم، مقدار آن را مثبت بی‌نهایت (منفی بی‌نهایت) می‌کنیم. سپس کافی است راس‌های روی مسیر بین آن عنصر و ریشه از پایین به بالا مقدار گرفته شده از فرزند خود را با مقدار ذخیره شده در خود مقایسه کرده و بازنده را در خود ذخیره کرده و برنده را به پدر خود دهند تا درخت جدید ساخته شود. چون ارتفاع درخت از ${\displaystyle O(\log n)}$ است زمان حذف از ${\displaystyle O(\log n)}$ می‌شود.

• جایگزینی عنصر کمینه (بیشینه): ${\displaystyle O(\log n)}$
  

زمانی که بخواهیم عنصر کمینه (بیشینه) را جایگزین کنیم، مقدار جدید را به آن می‌دهیم. سپس راس‌های روی مسیر بین آن عنصر و ریشه از پایین به بالا مقدار گرفته شده از فرزند خود را با مقدار ذخیره شده در خود مقایسه کرده و بازنده را در خود ذخیره کرده و برنده را به پدر خود می‌دهند تا درخت جدید ساخته شود. چون ارتفاع درخت از ${\displaystyle O(\log n)}$ است زمان جایگزینی نیز از ${\displaystyle O(\log n)}$ می‌شود.

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

import math
def rec_build(A, B, x, l, r):
    if l == r:
        B[x] = (A[l], x)
        return B[x]
    else:
        mid = (l + r) // 2
        a = rec_build(A, B, 2 * x, l, mid)
        b = rec_build(A, B, (2 * x) + 1, mid + 1, r)
        if b[0] < a[0]:
            B[x] = a
            return b
        else:
            B[x] = b
            return a

def build(A):
    n = len(A)
    tree = [None] * (2 ** (math.ceil(math.log2(n)) + 1))
    tree[0] = rec_build(A, tree, 1, 0, n - 1)
    return tree

def pop(B):
    result = B[0][0]
    index = B[0][1]
    B[index] = None
    minimum = None
    while index > 1:
        index = index // 2
        if minimum is None:
            minimum, B[index] = B[index], minimum
        elif B[index] is None:
            pass
        else:
            minimum, B[index] = min(B[index], minimum), max(B[index], minimum)
    B[0] = minimum
    return result

def minimum(B):
    return B[0][0]

def replace_minimum(B, value):
    result = B[0][0]
    index = B[0][1]
    B[index] = (value, index)
    minimum = B[index]
    while index > 1:
        index = index // 2
        if minimum is None:
            minimum, B[index] = B[index], minimum
        elif B[index] is None:
            pass
        else:
            minimum, B[index] = min(B[index], minimum), max(B[index], minimum)
    B[0] = minimum
    return result

A = [-8, 3, 17, 57, 0, -19, 21, 5, 965 , 2, 0, 1, 34, 83]
B = build(A)
print(replace_minimum(B, -7))
print(pop(B))
print(minimum(B))