Python Help. I have an issue with my priority queue. I can\'t seem to get my res
ID: 3710651 • Letter: P
Question
Python Help. I have an issue with my priority queue. I can't seem to get my result to match the "solution" set. I believe the issue is with the upheap function. I believe I am implementing it incorrectly.
class PriorityQueue:
def __init__(self, entries=None, key=lambda x: x):
self._entries = list(entries or [])
self.key = key
self._heapify()
def insert(self, item):
self._entries.append(item)
self._upheap(len(self))
def _parent(self, i):
return (i - 1) // 2
def _children(self, i):
left, right = 2 * i + 1, 2 * i + 2
return range(left, min(len(self), right + 1))
def findtop(self):
try:
return self._entries[0]
except:
return None
def removetop(self):
L = self._entries
if len(L) == 0:
return None
self._swap(0, len(L) - 1)
item = L.pop()
self._downheap(0)
return item
def _swap(self, a, b):
L = self._entries
L[a], L[b] = L[b], L[a]
def _upheap(self, i):
L=self._entries
parent=self._parent(i)
print(L[i])
print(L[parent])
s=min(L[parent],L[i], key=self.key)
if i>0 and L[i]<L[parent]:
self._swap(i,parent)
self._upheap(parent)
def _downheap(self, i):
L=self._entries
children=self._children(i)
if children:
child=min(children, key=lambda x:L[x])
if L[child]<L[i]:
self._swap(i,child)
self._downheap(child)
pass
def __len__(self):
return len(self._entries)
def _heapify(self):
for i in range(len(self)):
self._downheap(len(self) - i - 1)
def update(self, other):
self._entries.extend(other._entries)
self._heapify()
pass
def _isheap(self):
return all(self._entries[i] >= self._entries[(i - 1) // 2] for i in range(1, len(self._entries)))
pass
if __name__ == '__main__':
ent = [[10, 'p', 100], [1, 'q', 10], [10, 's', 99], [1, 'r', 1],[2, 'x', 6], [2, 't', 33], [10, 'z', 1000], [1000, 'w', 2]]
solution = [[100, 'c', 100], [10, 'p', 100], [10, 's', 99], [1, 'q', 10],[2, 'x', 6],
[2, 't', 33], [10, 'z', 1000], [1000, 'w', 2], [1, 'r', 1]]
pq = PriorityQueue(ent, lambda x:x[1])
print(pq._entries)
pq._entries.append([100, 'c', 100])
pq._upheap(8)
print(pq._entries)
Explanation / Answer
def _upheap(self, i):
L=self._entries
parent=self._parent(i)
print(L[i])
print(L[parent])
s=min(L[parent],L[i], key=self.key)
if i>0 and L[i]>L[parent]:
self._swap(i,parent)
self._upheap(parent)
there was the problem o n if condition why are checking for less tham parent if should be always gteterthan parent to sap and remove
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.