Heap bug hunt

Questions 1 to 5 of 8

1. 1. This heap should be a min-heap. Adding 5, 1, 9 and 3, then polling, prints 9 5 3 1 instead of 1 3 5 9. Which line causes it? ``python def before(self, x, y): return x > y def add(self, x): self.a[self.size] = x i = self.size self.size += 1 while i > 0: p = (i - 1) // 2 if not self.before(self.a[i], self.a[p]): break self.swap(i, p) i = p ``

   self.a[self.size] = x, because the new value is written to the wrong slotreturn x > y, because it puts the larger value firstp = (i - 1) // 2, because the parent index formula is wrongif not self.before(self.a[i], self.a[p]): break, because the loop stops at the wrong time
2. 2. The add method in this heap is correct. Adding 5, 1, 9, 3, 7, 2 and 8 in that order, then polling until the heap is empty, prints 1 2 7 8 5 9 3, which is out of order. Which line in poll causes it? ``python def poll(self): top = self.a[0] self.size -= 1 self.a[0] = self.a[self.size] i = 0 while True: l = 2 * i r = 2 * i + 2 best = i if l < self.size and self.before(self.a[l], self.a[best]): best = l if r < self.size and self.before(self.a[r], self.a[best]): best = r if best == i: break self.swap(i, best) i = best return top ``

   self.a[0] = self.a[self.size], because the last value should be moved to the end of the listif best == i: break, because the loop should never stopself.swap(i, best), because swap should run before the comparisonsl = 2 * i, because the left child should be 2 * i + 1
3. 3. The code prints b(3), but a should come first now. What is the bug? Task compares by its priority field in __lt__. ``python import heapq class Task: def __init__(self, priority, name): self.priority = priority self.name = name def __lt__(self, other): return self.priority < other.priority def __repr__(self): return f"{self.name}({self.priority})" heap = [] a = Task(5, "a") b = Task(3, "b") c = Task(8, "c") heapq.heappush(heap, a) heapq.heappush(heap, b) heapq.heappush(heap, c) a.priority = 1 print("peek:", heap[0]) # prints b(3) ``

   __lt__ should return self.priority > other.priority, so the largest priority comes firstpeek should use heapq.heappop, because heap[0] returns a copy of the wrong taska.priority is changed while a is still in the heap, so the heap order breaks and heap[0] does not noticeTask must define __eq__, so heapq can find a again
4. 4. Adding 17 values to this heap raises IndexError: list assignment index out of range. What is missing? ``python class Heap: def __init__(self): self.a = [None] * 16 self.size = 0 def add(self, x): self.a[self.size] = x i = self.size self.size += 1 while i > 0: p = (i - 1) // 2 if self.a[i] >= self.a[p]: break self.a[i], self.a[p] = self.a[p], self.a[i] i = p ``

   A break in the sift-up loop, so the loop stops at the rootA larger parent index, so the new value goes to a lower slotA check that self.size == len(self.a) before the write, which grows the list with extend when it is fullself.a = [] in __init__, because a list cannot start with a fixed size
5. 5. What does this print? ``python def is_min_heap(a, size): for i in range(1, size): if a[(i - 1) // 2] > a[i]: return False return True print(is_min_heap([7, 3, 8, 5, 9], 5)) ``

   FalseTrue7an IndexError