Реализация алгоритма PriorityQueue

Question

Вот моя реализация алгоритма PriorityQueue.У меня такое чувство, что моя поп-функция невернаНо я не уверен, где именно это не так.Я несколько раз проверял, где моя логика пошла не так, но она кажется совершенно правильной (проверено с помощью псевдокода CLRS).

class PriorityQueue:
"""Array-based priority queue implementation."""
def __init__(self):
    """Initially empty priority queue."""
    self.queue = []
    self.min_index = None

def parent(self, i):
    return int(i/2)

def left(self, i):
    return 2*i+1

def right(self, i):
    return 2*i+2

def min_heapify(self, heap_size, i):
    #Min heapify as written in CLRS
    smallest = i
    l = self.left(i)
    r = self.right(i)
    #print([l,r,len(self.queue),heap_size])

    try:
        if l <= heap_size and self.queue[l] < self.queue[i]:
            smallest = l
        else:
            smallest = i
    except IndexError:
        pass
    try:
        if r <= heap_size and self.queue[r] < self.queue[smallest]:
            smallest = r

    except IndexError:
        pass

    if smallest != i:
        self.queue[i], self.queue[smallest] = self.queue[smallest], self.queue[i]
        self.min_heapify(heap_size, smallest)

def heap_decrease_key(self, i, key):
    #Implemented as specified in CLRS
    if key > self.queue[i]:
        raise ValueError("new key is larger than current key")

    #self.queue[i] = key

    while i > 0 and self.queue[self.parent(i)] > self.queue[i]:
        self.queue[i], self.queue[self.parent(i)] = self.queue[self.parent(i)], self.queue[i]
        i = self.parent(i)

def __len__(self):
    # Number of elements in the queue.
    return len(self.queue)

def append(self, key):
    """Inserts an element in the priority queue."""
    if key is None:
        raise ValueError('Cannot insert None in the queue')
    self.queue.append(key)
    heap_size = len(self.queue)
    self.heap_decrease_key(heap_size - 1, key)

def min(self):
    """The smallest element in the queue."""
    if len(self.queue) == 0:
        return None
    return self.queue[0]

def pop(self):
    """Removes the minimum element in the queue.

    Returns:
        The value of the removed element.
    """
    if len(self.queue) == 0:
        return None
    self._find_min()
    popped_key = self.queue[self.min_index]
    self.queue[0] = self.queue[len(self.queue)-1]
    del self.queue[-1]
    self.min_index = None
    self.min_heapify(len(self.queue), 0)
    return popped_key

def _find_min(self):
    # Computes the index of the minimum element in the queue.
    #
    # This method may crash if called when the queue is empty.
    if self.min_index is not None:
        return
    min = self.queue[0]
    self.min_index = 0

Любая подсказка или ввод будут высоко оценены

Answer 1

Основная проблема в том, что функция parent неверна.Как и в случае с методами left и right, вы должны сначала вычесть 1 из i перед тем, как вдвое уменьшить это значение:

def parent(self, i):
    return int((i-1)/2)

Другие примечания:

• Вы не очень хорошо пользуетесь участником self.min_index.Это либо 0, либо None, и различие на самом деле не используется в вашем коде, как это непосредственно следует из того, пуста ли куча или нет.Это также означает, что вам не нужен метод _find_min (что само по себе странно: вы присваиваете min, но никогда не используете его).В любом случае, отбросьте этот метод и строку, где вы его вызываете.Также опустите строку, где вы присваиваете None значение self.min_index, и единственное другое место, где вы читаете значение, просто используйте 0.

• У вас естьдва способа защиты от ошибок индекса в методе min_heapify: <= heapsize и блок try.Первая защита должна иметь < вместо <=, но вы должны использовать только один способ, а не два.Так что либо тестируйте менее чем, или ловушку исключения.

• Блок else с smallest = i не нужен, потому что в это время smallest == i.

• min_heapify имеет первый параметр, который всегда получает полный размер кучи.Так что это ненужный параметр.Также не имеет смысла когда-либо вызывать этот метод с другим значением для него.Поэтому удалите этот аргумент из определения метода и всех вызовов.А затем определите heap_size = len(self.queue) как локальное имя в этой функции

• В heap_decrease_key вы закомментировали присваивание #self.queue[i] = key, что хорошо, если вы никогда не вызываете этот метод длядействительно уменьшение ключ.Но хотя вы никогда не делаете это изнутри класса, пользователь класса вполне может захотеть использовать его таким образом (поскольку именно это предлагает имя метода).Так что лучше раскомментируйте это назначение.

• С учетом вышеуказанных изменений ваш экземпляр будет иметь только queue в качестве свойства данных.Это нормально, но вы можете позволить PriorityQueue наследовать от list, так что вам это свойство тоже не нужно, и вы можете просто работать со списком, который вы наследуете.Следовательно, вам следует заменить self.queue на self во всем коде, и вы можете отбросить методы __init__ и __len__, так как реализация list - это то, что вам нужно.Немного осторожности требуется в том случае, если вы хотите вызвать list оригинальный метод, когда вы его переопределили, например, append.В этом случае используйте super().append.

Со всеми вышеуказанными изменениями:

class PriorityQueue(list):
    """Array-based priority queue implementation."""
    def parent(self, i):
        return int((i-1)/2)

    def left(self, i):
        return 2*i+1

    def right(self, i):
        return 2*i+2

    def min_heapify(self, i):
        #Min heapify as written in CLRS
        heap_size = len(self)
        smallest = i
        l = self.left(i)
        r = self.right(i)

        if l < heap_size and self[l] < self[i]:
            smallest = l
        if r < heap_size and self[r] < self[smallest]:
            smallest = r

        if smallest != i:
            self[i], self[smallest] = self[smallest], self[i]
            self.min_heapify(smallest)

    def heap_decrease_key(self, i, key):
        #Implemented as specified in CLRS
        if key > self[i]:
            raise ValueError("new key is larger than current key")

        self[i] = key

        while i > 0 and self[self.parent(i)] > self[i]:
            self[i], self[self.parent(i)] = self[self.parent(i)], self[i]
            i = self.parent(i)

    def append(self, key):
        """Inserts an element in the priority queue."""
        if key is None:
            raise ValueError('Cannot insert None in the queue')
        super().append(key)
        heap_size = len(self)
        self.heap_decrease_key(heap_size - 1, key)

    def min(self):
        """The smallest element in the queue."""
        if len(self) == 0:
            return None
        return self[0]

    def pop(self):
        """Removes the minimum element in the queue.

        Returns:
            The value of the removed element.
        """
        if len(self) == 0:
            return None
        popped_key = self[0]
        self[0] = self[-1]
        del self[-1]
        self.min_heapify(0)
        return popped_key

Answer 2

Ваша parent функция уже неверна.

Корневой элемент вашей кучи хранится в индексе массива 0, дочерние элементы - в 1 и 2. Родитель 1 - 0, это правильно,но родительский элемент для 2 также должен быть 0, тогда как ваша функция возвращает 1.

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

parent(i): i // 2
left_child(i): 2 * i
right_child(i): 2 * i + 1