Implementing a PriorityQueue Algorithm

Question

Here is my implementation of a PriorityQueue algorithm. I have a feeling that my pop function is wrong. But I am not sure where exactly it is wrong. I have checked multiple times on where my logic went wrong but it seems to be perfectly correct(checked with CLRS pseudo code).

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

Any hint or input will be highly appreciated

trincot · Accepted Answer

The main issue is that the parent function is wrong. As it should do the opposite from the left and right methods, you should first subtract 1 from i before halving that value:

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

Other things to note:

You don't really have a good use for the member self.min_index. It is either 0 or None, and the difference is not really used in your code, as it follows directly from whether the heap is empty or not. This also means you don't need the method _find_min, (which in itself is strange: you assign to min, but never use that). Any way, drop that method, and the line where you call it. Also drop the line where you assign None to self.min_index, and the only other place where you read the value, just use 0.
You have two ways to protect against index errors in the min_heapify method: <= heapsize and a try block. The first protection should really have < instead of <=, but you should use only one way, not two. So either test the less-than, or trap the exception.
The else block with smallest = i is unnecessary, because at that time smallest == i.
min_heapify has a first parameter that always receives the full size of the heap. So it is an unnecessary parameter. It would also not make sense to ever call this method with another value for it. So drop that argument from the method definition and all calls. And then define heap_size = len(self.queue) as a local name in that function
In heap_decrease_key you commented out the assignment #self.queue[i] = key, which is fine as long as you never call this method to really decrease a key. But although you never do that from "inside" the class, the user of the class may well want to use it in that way (since that is what the method's name is suggesting). So better uncomment that assignment.
With the above changes, your instance would only have queue as its data property. This is fine, but you could consider to let PriorityQueue inherit from list, so that you don't need this property either, and can just work with the list that you inherit. By consequence, you should then replace self.queue with self throughout your code, and you can drop the __init__ and __len__ methods, since the list implementation of those is just what you need. A bit of care is needed in the case where you want to call a list original method, when you have overridden it, like append. In that case use super().append.

With all of the above changes applied:

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

Implementing a PriorityQueue Algorithm

Answers (2)

Related Questions