Написание минимальной кучи в 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а затем вернуть set принадлежащий 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() на нем это должно привести к куче, которая больше похожа на:

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

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

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

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

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

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: Пустая куча. Вернуть пустой список.

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

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 (значения, X)

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

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

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

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

толкать()

_percolate_up()

_percolate_down()

_min_child()

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

пустой()

поп()

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

Топ()

уровни()

most_common_x (значения, X)

Самый простой способ начать работу с Python

Делаем целые числа Python итерируемыми | Кодементор

Лучшие языки программирования для изучения в 2021 году

Как я изучил машинное обучение

Начало работы с картой | Кодементор

Введение в алгоритм BRKGA-MP-IPR

Добавить комментарий Отменить ответ

толкать()

_percolate_up()

_percolate_down()

_min_child()

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

пустой()

поп()

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

Топ()

уровни()

most_common_x (значения, X)

Похожие записи

Добавить комментарий Отменить ответ