Heap review

Questions 1 to 5 of 6

1. 1. What does this program print? ``python import heapq meetings = [(1, 4), (4, 6), (2, 3), (5, 7)] meetings.sort(key=lambda m: m[0]) end_times = [] best = 0 for start, end in meetings: while end_times and end_times[0] <= start: heapq.heappop(end_times) heapq.heappush(end_times, end) best = max(best, len(end_times)) print(best) ``

   2413
2. 2. A Job dataclass compares on priority and then arrival. The name field is kept but left out of the comparison. The code below pushes four jobs and pops them until the heap is empty, printing each name. ``python import heapq from dataclasses import dataclass, field @dataclass(order=True) class Job: name: str = field(compare=False) priority: int arrival: int heap = [] for job in [Job("P", 2, 7), Job("Q", 1, 9), Job("R", 2, 3), Job("S", 1, 4)]: heapq.heappush(heap, job) while heap: print(heapq.heappop(heap).name, end=" ") ``

   S Q P RP R Q SS Q R PQ S R P
3. 3. Which of these ways of putting ints into a heapq make heappop return the largest value first? Pick all that apply.

   Pick every answer that is true.

   heapq.heappush(h, -x), then print -heapq.heappop(h)heapq.heappush(h, x), then print heapq.heappop(h)heapq.heappush(h, (-x, x)), then print heapq.heappop(h)[1]heapq.heappush(h, (x, -x)), then print heapq.heappop(h)[0]
4. 4. Using the heap method from the meeting-rooms lesson, how many rooms does this set of meetings need? [0, 10], [1, 5], [2, 6], [7, 8], [9, 12]

   Type a number.

5. 5. A plain class Job with no ordering is pushed into a heapq twice. The first heappush works, but the second raises TypeError. Why? ``python import heapq class Job: def __init__(self, name): self.name = name heap = [] heapq.heappush(heap, Job("A")) heapq.heappush(heap, Job("B")) # TypeError ``

   A class instance cannot be stored in a heapq, even if it has a __lt__ method.The first push fills the list, so the second push has no room left.heapq compares the new item with an existing one using <, and a plain Job has no __lt__ method, so the comparison fails.heapq can only store numbers, so any other object causes a TypeError.