Реализация биномиальной кучи в Python 2.7

Question

Я ищу реализацию биномальной кучи на Python, и я заметил, что коды не имеют reduceKey. Почему в Binomial Heap никто не реализует lessKey? Реализация

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