python - deleting element at index i from heap

Question

I am trying to write a delete function for a heap. I am given a head class and heapify functions to work with, I just need to implement delete. I want to implement it in O(log n) time. This is what I've tried:

from heap import *
class heap_delete(heap):
    def delete(self, i):
        self.A[i] = self.A[-1] #put the bottom rightmost element in i
        self.min_heapify(i)

but when I run it with the provided test code, it says 'failed'. Reading the AssertionError statement it seems that nothing is happening to the index I am trying to manipulate. Here is the heap code I am importing:

def parent(i):
    return int(i/2)
def left(i)
    return 2*i
def right(i):
    return 2*i+1
class heap:
    def __init__(self):
        self.A = [None] #to make it 1 based, None is stuck at 0
    def __getitem__(self, i):
        return self.A[i]
    def min_heapify(self, i):
        l = left(i)
        r = right(i)
        smallest = i
        if l <= self.heapsize and self.A[l] < self.A[i]:
            smallest = l
        if r <= self.heapsize and self.A[r] < self.A[smallest]:
            smallest = r
        if smallest != i:
            self._swap(i, smallest)
            self.min_heapify(smallest)
    def _swap(self, index1, index2):
        self.A[index1], self.A[index2] = self.A[index2], self.A[index1]

There are other functions, such as decrease_key, extract_min, and insert. I can add them to the post if necessary but I believe everything I need is here. The AssertionError I am recieving is as follows:

    self.assertEquals(h.A, [None])
AssertionError: Lists differ: [None, 5] != [None]

and

    self.assertEquals(h.A, [None])
AssertionError: Lists differ: [None, 15] != [None]

the former AssertionError is from the test function I am supposed to run my code with. It calls h.insert(5) and h.delete(1), followed by self.assertEquals(h.A, [None]). The ladder, also in the test function, calls insert on 5,15,10,and 0 which is followed by h.delete(h.A.index(10)) and then the same assertEquals statement as before. From this I am lead to believe that my delete function isn't deleting anything. I have tried using del and the _swap provided but perhaps did not use them correctly. Again I am looking for O(log n) time so if anyone could point me in the right direction that would be great.

Possible duplicate of [Python: delete element from heap](http://stackoverflow.com/questions/10162679/python-delete-element-from-heap) — donut juice, Feb 19 '16 at 20:00

score 1 · Accepted Answer · answered Feb 19 '16 at 00:02

1

def delete(self, i):
    self.A[i] = self.A[-1] #put the bottom rightmost element in i
    del self.A[-1]         # <--- shrink the list
    self.min_heapify(i)

answered Feb 19 '16 at 00:02

aghast

14,785
3
24
56

I can't believe I forgot to delete the old element! I feel so silly. I added the `del` statement and also added a `self.heapsize -= 1` to finish it off. – donut juice Feb 19 '16 at 19:58

score -1 · Answer 2 · answered Feb 18 '16 at 22:46

-1

When you delete from your heap, then your array size should go down. That is currently not happening in your delete function :).

answered Feb 18 '16 at 22:46

Untitled123

1,317
7
20

Would a `self.heapsize -= 1` statement remedy this? – donut juice Feb 18 '16 at 22:50
well your list is A..so you need to do a delete somewhere also – Untitled123 Feb 18 '16 at 22:51
Isn't setting the bottom rightmost element (`A[-1]`) as `A[i]` doing this? Or should I just flat out 'del A[i]`? – donut juice Feb 18 '16 at 22:52
self.A[i] = self.A[-1] #put the bottom rightmost element in i If this is what you're referring to, then you are just copying over the last element into the position at i. This is correct, but only half the story (even after you heapify). The bottom element still exists at A[-1] after being copied, do you see the problem? – Untitled123 Feb 18 '16 at 22:53
To expand a bit more, trace your code with a random heap such as A=[10,4,6,1,2,1,2] and delete the 3rd element, then delete the new 3rd element again. – Untitled123 Feb 18 '16 at 22:56

python - deleting element at index i from heap

2 Answers2