How to call heapify_up function in Python?

Question

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

Martijn Pieters · Accepted Answer · 2014-07-06 21:22:25Z

2

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.

edited Jul 6, 2014 at 21:22

answered Jul 6, 2014 at 20:50

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

user3810193 Over a year ago

Sorry I don't get it. I didn't use self.heap when I called the function. I assigned a list to x.sorting_key. How does it affect calling x.hepify_up ?

Martijn Pieters Over a year ago

@user3810193: Your self.heap attribute is an empty list, but you are trying to index it with self.heap[child] and self.heap[parent]. An empty list has no elements in it, so you cannot index into it. You normally initialize your heap from an existing list. Your sorting_key attribute is used as an attribute on the heap elements in getattr() calls, attributes can never be lists, so something is really messed up here. Do you understand at all what self.heap and self.sorting_key are meant to do in this code?

user3810193 Over a year ago

Thanks Martijin. I don't quite know how to initialize the heap with an existing list (assign it to self.heap). Can you give an example? I tried x=Heap(), x.heap([list]), which seemed wrong too.

Martijn Pieters Over a year ago

@user3810193: x = Heap(attribute_name) then x.heap = [element1, element2, ...]. But your heap needs to contain objects with an attribute that gives the sort value.

user3810193 Over a year ago

I'm sorry can you explain what does it mean "contain objects with an attribute that gives the sort value"? Basically I want to know using the class, how to create an list (eg [16,4,10,14,7,9,3,2,8,1]) and heapify it by swapping index[2] with index[5].

|

Collectives™ on Stack Overflow

How to call heapify_up function in Python?

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related