Блог

Я пытаюсь вызвать заданную функцию «heapify_up», которая передает значение вверх по куче. она сравнивает значение, первоначально указанное в индексе i кучи, с его родительскими значениями, и, если свойство кучи нарушено, меняет их местами.

Я продолжал получать ошибку :

 File "try.py", line 30, in heapify_up
    while (getattr(self.heap[parent], self.sorting_key) <
IndexError: list index out of range
  

ниже приведен мой код

 class Heap:
    def __init__(self, sorting_key):
        """Initializes a new instance of a heap.

        Args:
            sorting_key: Specifies the attribute of the object inserted
            into the heap, on the basis of which the heap was created.
        """
        self.heap = list()
        self.mapping = dict()
        self.sorting_key = sorting_key

    def heapify_up(self, child):
        """Standard heapify operation, as described in CLRS.
        Works by swapping the element originially at index child in the heap
        with its parent until the heap property is satisfied. Modifies the
        appropriate heap attribute

        Args:
            child: Index of the element that violates the heap property

        Returns:
            None
        """
        parent = (child - 1) / 2
        # Swaps the element originally at the index child with its parent
        # until the value of the specifed attribute of the parent is greater
        # than the value of the specified attribute of the element itself
        while (getattr(self.heap[parent], self.sorting_key) <
               getattr(self.heap[child], self.sorting_key)):
            if (parent == -1):
                # This means child was 0, which means we have reached the
                # top of the heap
                return

            # Swap the mappings as well to ensure that future references in
            # the mapping dict refer to the correct position of the object in
            # the heap
            self.mapping[self.heap[parent].player] = child
            self.mapping[self.heap[child].player] = parent

            # Swap the parent and the child
            temp = self.heap[parent]
            self.heap[parent] = self.heap[child]
            self.heap[child] = temp

            # Move the child and parent pointers up the heap
            child = parent
            parent = (child - 1) / 2

x=Heap([16,4,10,14,7,9,3,2,8,1])  # sample list
x.heapify_up(4)  # index of child that violates the heap property
print x.sorting_key
  

Вы оставляете self.heap пустой список. Любой индекс выдаст IndexError исключение:

 class Heap:
    def __init__(self, sorting_key):
        # ...
        self.heap = list()
  

Вместо этого ваш список присваивается sorting_key , что не соответствует документированному использованию для sorting_key :

 sorting_key: Specifies the attribute of the object inserted
into the heap, on the basis of which the heap was created.
  

Ваш код предполагает наличие списка объектов с атрибутами, названными в sorting_key атрибуте. Но затем ваш код передает список целых чисел и не содержит ключа сортировки. heapify_up Функция также ожидает, что элементы кучи будут иметь .player атрибут, которого также нет у целых чисел. Этот код никогда не сможет работать с введенными вами данными!

Вам нужно будет определить, какое состояние вам Heap необходимо отслеживать, и исправить это, прежде чем зацикливаться на heap_up методе.

Обратите внимание, что стандартная библиотека Python уже поставляется с heapq модулем; документация ссылается на исходный код, который является универсальным и не привязан к определенному типу элемента кучи, как представляется, этот код.