CODEWITHSUNDEEP
pythonalgorithmheap
user3810193
user3810193

Reputation: 53

How to call heapify_up function in Python?

I'm trying to call a given function "heapify_up" which trickles a value up the heap. it compare the value originally at index i of the heap with its parents, and if the heap property is violated, swaps the two.

I kept getting error : 

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

below is my code 

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

Upvotes: 0

Views: 219

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1121774

You leave self.heap an empty list. Any index will throw an IndexError exception:

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

Your list is instead assigned to sorting_key, which doesn't match with the documented use for sorting_key:

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

Your code assumes a list of objects with attributes, named in the sorting_key attribute. But your code then passing in a list of integers and no sorting key. The heapify_up function also appears to expect the heap elements to have a .player attribute, which integers do not have either. This code can never work with the inputs you gave!

You'll need to work out what state your Heap needs to track and fix that before fixating on the heap_up method.

Note that the Python standard library already comes with a heapq module; the documentation links to the source code, which is generic and not tied to a specific heap element type as this code appears to be.

Upvotes: 2

Related Questions