Написание минимальной кучи в Python3

Прежде чем я начну, если вам нужна какая-то информация о том, что такое куча:

Это обсуждение касается минимальной кучи .

Недавно я провел последнюю неделю, помогая одному из моих платящих студентов написать структуру данных с минимальной кучей в Python3.

Дано следующее определение класса для узла:

class Node:
    """
    Class definition shouldn't be modified in anyway
    """
    __slots__ = ('_key', '_val')

    def __init__(self, key, val):
        self._key = key
        self._val = val

    def __lt__(self, other):
        return self._key < other._key or (self._key == other._key and self._val < other._val)

    def __gt__(self, other):
        return self._key > other._key or (self._key == other._key and self._val > other._val)

    def __eq__(self, other):
        return self._key == other._key and self._val == other._val

    def __str__(self):
        return '(k: {0} v: {1})'.format(self._key, self._val)

    __repr__ = __str__

    @property
    def val(self):
        """
        :return: underlying value of node
        """
        return self._val

Уметь определять отсутствующие методы в структуре данных с минимальной кучей:

class Heap:
    """
    Class definition is partially completed.
    Method signatures and provided methods may not be edited in any way.
    """
    __slots__ = ('_size', '_capacity', '_data')

    def __init__(self, capacity):
        self._size = 0
        self._capacity = capacity + 1  # additional element space for push
        self._data = [None for _ in range(self._capacity)]

    def __str__(self):
        return ', '.join(str(el) for el in self._data if el is not None)

    __repr__ = __str__

    def __len__(self):  # allows for use of len(my_heap_object)
        return self._size

#    DO NOT MODIFY ANYTHING ABOVE THIS LINE
#    Start of Student Modifications

    def _percolate_up(self):
        pass

    def _percolate_down(self):
        pass

    def _min_child(self, i):
        pass

    def push(self, key, val):
        pass

    def pop(self):
        pass

    @property  # do not remove
    def empty(self):
        pass

    @property  # do not remove
    def top(self):
        pass

    @property  # do not remove
    def levels(self):
        pass

Кроме того, есть функция, которую мы хотим написать вне самого класса Heap , def most_common_x(vals , X): , которая будет принимать список значений vals , а затем возвращать набор из X наиболее распространенных значений в списке.

def most_common_x(vals, X):
  pass

Я собираюсь пройти через каждый метод, один за другим, так же, как я сделал это со своим учеником.

Важно тестировать свой код по ходу работы, а не просто полагаться на автоматические решения для тестирования. Знайте, как вручную протестировать и проверить, что вывод метода-это то, что вы хотите, прежде чем предполагать, что что-то работает.

Давайте начнем!

толкать()

push() зависит от _percolate_up() , в противном случае мы могли бы просто написать:

def push(self, key, val):
        self._data[self._size] = Node(key,val)
        self._size += 1

и будет сделано.

Это позволило бы нам создать действительно простую кучу:

h = Heap(4)
h.push(4, 'a')
h.push(2, 'b')
h.push(3, 'c')
h.push(1, 'd')

На этом этапе мы должны начать смотреть на _percolate_up() .

_percolate_up()

_percolate_up() заключается в замене нижнего узла его родительскими узлами до тех пор, пока его родители больше не будут больше его.

Возьмите кучу выше. Если бы мы вызвали _percolate_up() на нем, это должно привести к куче, которая больше похожа на:

Итак, нам нужно было бы начать с конца кучи.
Давайте создадим индекс и установим его равным последнему допустимому индексу в нашем списке данных.
Теперь давайте пройдемся по нашему списку, пока не доберемся до корневого узла:
- Захватите узел для нашего текущего индекса. Это ребенок .
- Вычислите родительский индекс , который является индексом i минус 1 делится на 2 в целом в .
- Захватите родительский узел с учетом его индекса.
- Если оба ребенок и родитель не являются Нет :
  - Если ребенок меньше, чем родитель :
    - Поменяйте их местами
- Обновите индекс, чтобы он указывал на родителя

def _percolate_up(self):
    i = self._size - 1
    while i/2 > 0:
        child = self._data[i]
        parentIndex = (i-1)//2
        parent = self._data[parentIndex]
        if child is not None and parent is not None:
            if child < parent:
                tmp = parent
                self._data[parentIndex] = child
                self._data[i] = tmp 
        i = parentIndex

_percolate_down()

Оказывается, что push() также зависит от pop() , который зависит от _percolate_down() .

Оказывается, что _percolate_down() зависит от _min_child() !

_min_child()

Это просто вопрос терпеливого рассмотрения каждого дела.

Если пусто
Если “дочерний” индекс выходит за рамки
Если данный индекс не имеет узла
Если у узла нет детей
Если узел имеет только левый дочерний элемент
Если у узла есть только правильный дочерний элемент
Если у узла есть оба ребенка

На самом деле это зависит от empty () , но мы сделаем это через минуту.

def _min_child(self, i):
  if self.empty:
      return -1
  if i*2+1 > self._size:
      return -1
  if self._data[i] is None:
      return -1
  left = i*2+1
  right = i*2+2
  left_val = self._data[left]
  right_val = self._data[right]
  if left_val is None and right_val is None:
      return -1
  if left_val is not None and right_val is None:
      return left
  if left_val is None and right_val is not None:
      return right
  if self._data[left] < self._data[right]:
      return left
  return right

вернуться к _percolate_down()

Итак, на этот раз, шагая по ветвям дерева в противоположном направлении к _percolate_up() :

Пока мы не в конце кучи:
- Возьмите минимального ребенка
- Если допустимо и текущий узел больше минимального дочернего:
  - Поменяйте их местами
- Обновите индекс, чтобы указать минимальный индекс ребенка

def _percolate_down(self):
    i = 0
    while i*2 <= self._size-1:
        mc = self._min_child(i)
        if mc == -1:
            break
        if self._data[i] > self._data[mc]:
            tmp = self._data[i]
            self._data[i] = self._data[mc]
            self._data[mc] = tmp
        i = mc

пустой()

Супер просто давайте выбьем его:

def empty(self):
    if self._size == 0:
        return True
    return False

хлопок()

Теперь , когда мы написали _percolate_down() и empty () , мы можем позаботиться об этом.

Если куча пуста, верните None
Наше возвращаемое значение-это просто головной узел или начало нашего списка данных
Замените передний узел на конец нашей кучи/последнее значение/узел
Размер декремента
Очистите последний элемент (фактически мы меняем местами самый маленький и самый большой элементы, затем обнуляем последний узел…)
Просочите головной узел вниз в его новое положение

def pop(self):
    if self.empty:
        return None
    rv = self._data[0].val
    self._data[0] = self._data[self._size-1]
    self._size -= 1
    self._data[self._size] = None
    self._percolate_down()
    return rv

вернуться к толчку()

С обоими pop() и _percolate_up() мы позаботились, пришло время позаботиться о push() :

Создайте новый Узел в последней позиции в нашей куче
Увеличение размера кучи
Просочите новый узел в соответствующее положение
Если мы достигли пропускной способности, вытащите самый маленький узел

def push(self, key, val):
    self._data[self._size] = Node(key,val)
    self._size += 1
    self._percolate_up()
    if self._size == self._capacity:
        self.pop()

верхний()

Тоже очень просто. Просто захватите верхний узел, пока куча не пуста.

def top(self):
    if self.empty is False:
      return self._data[0].val
    return None

уровни()

Этот немного длиннее.

Уровни должны возвращать список списков с узлами каждого уровня кучи в каждом списке (таким образом, по одному списку на уровень).

Крайний случай 1: Пустая куча. Верните пустой список.

Начните с начала кучи
Создайте новый список для этого уровня
Если это первый список, к которому мы добавляем:
- Добавьте корневой узел в список первого уровня
- Добавьте список первого уровня в наш список возврата
Ещё:
- Вычислите индексы startIndex и endIndex этого уровня в списке данных нашей кучи
- Добавьте каждый узел в наш список уровней
- Если список уровней не пуст, добавьте его в наш список возврата

def levels(self):
    ourList = []
    if self.empty:
        return ourList
    prevStartIndex = 0
    while prevStartIndex < len(self._data):
        thisLevel = []
        if len(ourList) == 0:
            thisLevel.append(self._data[0])
            prevStartIndex = 0
            ourList.append(thisLevel)
        else:
            startIndex = (prevStartIndex * 2) + 1
            endIndex = startIndex * 2
            j = startIndex 
            while j < len(self._data) and j <= endIndex:
                node = self._data[j]
                if node is not None:
                    thisLevel.append(self._data[j])
                j += 1
            prevStartIndex = startIndex 
            if len(thisLevel) != 0:
                ourList.append(thisLevel)
    return ourList

Наконец, функция вне класса Heap :

most_common_x(vals, X)

Создайте пустой словарь
Для каждого элемента в vals:
- Подсчитайте его в словаре, увеличив его значение для ключа элемента
Создайте новую кучу
Учитывая ключи словаря:
- Возьмите значение словаря для каждого ключа, это количество раз, когда этот элемент появлялся в списке vals
- Толкни его в кучу
Выделите достаточное количество узлов, чтобы оставшиеся узлы были X в количестве
Добавьте оставшиеся узлы в возвращаемый набор

Код с некоторыми комментариями:

def most_common_x(vals, X):
    
    # step 1 - build the dictionary
    d = {}
    
    for element in vals:
        # check to see if there is a count for our given element
        # if not, return 0 for default
        count = d.get(element, 0)
        
        # increment count
        count += 1
        
        # re-assign new count back to dictionary
        d[element] = count
    
    # step 2 - build the heap from the dictionary
    d_keys = d.keys()
    heapSize = len(d_keys)
    heap = Heap(heapSize)
    
    for key in d_keys:
        count = d[key]
        heap.push(count, key)

    # step 3 - grab the leaf nodes and add to our return set
    returnSet = set()
    while len(heap) > X:
        heap.pop()

    while not heap.empty:
        returnSet.add(heap.pop())

    return returnSet

Это, по общему признанию, быстрая запись, но я всегда могу уточнить ее дальше, если вам нужны разъяснения, просто спросите!