CODEWITHSUNDEEP
pythonqueueheappriority-queue
PaperThin88
PaperThin88

Reputation: 13

Python Heap Priority Queue sift_up()

I am still rather new to Python, but am having a problem with a heap priority queue. Here are my init(), str(), add(), and my sift_up() method: 

def __init__(self):
    self.queue = []

def __str__(self):
    return str(self.queue)

def add(self, item):
    self.queue.append(item)
    self.sift_up(len(self.queue) - 1)

def sift_up(self, item):
    parent = (item - 1) // 2
    if parent >= 0 and self.queue[parent] > self.queue[item]:
        self.queue[parent], self.queue[item] = self.queue[item], self.queue[parent]
        self.sift_up(parent)

Now when I add items to the queue they go in fine. Say, I put this into terminal:

pq = PriorityQueue()
pq.add(1)
pq.add(2)
pq.add(45)
pq.add(4)
pq.add(41)
pq.add(5)

pq.__str__()

What I get back is '[1,2,5,4,41,45]'. So it looks to sift_up() only somewhat, it doesn't completely reorder the heap.

EDIT: It seems to get screwed up whenever I add a '1' to the queue. In this example I had it return after each add:

>>> pq.add(5)
[5]
>>> pq.add(53)
[5, 53]
>>> pq.add(531)
[5, 53, 531]
>>> pq.add(5131)
[5, 53, 531, 5131]
>>> pq.add(1)
[1, 5, 531, 5131, 53]
>>>

So it takes whatever element is at [1] and puts it to the back of the queue. I am sure this is trivial, but being new to Python, I can't seem to figure out why. Again, any help is greatly appreciated! Thanks.

Upvotes: 1

Views: 809

Answers (1)

ely
ely

Reputation: 77494

In your example data, [5, 53, 531, 5131], the computation as you have expressed it in sift_up will go like this:

# Append 1 to the end
--> [5, 53, 531, 5131, 1]

# The index for '1' is 4, so 'item' is 4.
# (4-1) // 2 = 1 (and 1 >= 0), so 'parent' is 1.
# The value at 'parent' is 53. 53 > 1 is true.
# So swap the value 53 with the value at the end of the list.
--> [5, 1, 531, 5131, 53]

# Now repeat, 'item' starts out at 1.
# The index at (1 - 1) // 2 = 0 (And 0 >=0) so 'parent' is 0.
# The value at index 0 is 5. 5 > 1 is true.
# So swap the value 5 with the value at 'item' (1) to get
--> [1, 5, 531, 5131, 53]

So this result follows logically from the way you've coded sift_up.

The standard library's heapq.heapify function also produces the same thing: it looks like this is the correct behavior for a priority queue:

In [18]: import heapq

In [19]: x = [5, 53, 531, 5131, 1]

In [20]: heapq.heapify(x)

In [21]: x
Out[21]: [1, 5, 531, 5131, 53]

Upvotes: 1

Related Questions