python - Python 2.7 中的二项式堆实现

Question

我正在寻找二项式堆的 Python 实现，我注意到代码没有实现 reduceKey。为什么在二项式堆中没有人实现 reduceKey？

Answer 1

示例实现：-

class Heap(object):
    def __init__(self, size):
        self.num = 0
        self.size = size
        self.data = [None] * size

    def __repr__(self):
        return '<Thing: %s>' % (self.data,)

    def insert(arr, x):
        if arr.num >= arr.size:
             return -1

        arr.num += 1
        i = arr.num
        arr.data[i] = x;
        while i:
            j = i >> 1
            if arr.data[i] > arr.data[j]:
                t = arr.data[i]
                arr.data[i] = arr.data[j]
                arr.data[j] = t
            else:
                break
            i = j
            return 0

    def left_child_idx(self, i):
        return ((i + 1) << 1) - 1

    def right_child_idx(self, i):
        return (((i + 1) << 1) + 1) - 1

    def check(self):
        i = 0
        while self.right_child_idx(i) < self.num:
            assert lessOrEq(self.data[self.left_child_idx(i)], self.data[i]), i
            assert lessOrEq(self.data[self.right_child_idx(i)], self.data[i]), i
            i = i == 0 and 1 or i << 1

def lessOrEq(a, b):
    if a is None or b is None:
        return True
    return a <= b

def build(ls):
    '''Builds a Heap from a list.'''
    t = Thing(len(ls)+1)
    for x in ls:
        t.insert(x)
    return t