бинарный поиск удалить мин - PullRequest
Новая
       15

бинарный поиск удалить мин

0 голосов
/ 04 июля 2018

Мне интересно в следующем коде,

В приведенном ниже коде для i задано значение min child, почему это делается вместо того, чтобы просто иметь i = i * 2. Оба способа «понижают» уровень двоичной кучи, мне просто любопытно, почему будет выбран минимум (если предположить, что оба дочерних элемента НЕ меньше родительского, почему выбирается меньший из двух больших дочерних элементов, а не один из них произвольно )

Для ясности эти методы ниже также относятся к классу двоичной кучи 

def percDown(self,i):
  while (i * 2) <= self.currentSize:
    mc = self.minChild(i)
    if self.heapList[i] > self.heapList[mc]:
      tmp = self.heapList[i]
      self.heapList[i] = self.heapList[mc]
      self.heapList[mc] = tmp
    i = mc

def minChild(self,i):
  if i * 2 + 1 > self.currentSize:
    return i * 2
  else:
    if self.heapList[i*2] < self.heapList[i*2+1]:
      return i * 2
    else:
      return i * 2 + 1

Код для класса двоичной кучи 

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    def delMin(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval
...