Medians and indexed heaps

Questions 1 to 5 of 7

1. 1. In the indexed heap from this lesson, what does one decrease-key cost when the heap holds n items?

   O(n), because the method searches the heap for the item firstO(1) to find the item by its id, then O(log n) to move it upO(log n) to find the item, then O(log n) to move it upO(n log n), because the heap is rebuilt after each change
2. 2. Python's heapq has no decrease-key. If you lower a key by pushing a second copy with heappush and skip the old copy when it comes out, what does the push cost, and what goes wrong?

   O(1), because heappush only writes to the end of the listO(n), because heapq must search the list for the old copy firstO(n log n), because heapq rebuilds the whole list on every pushO(log n) for the push, but the old copy stays in the list until it is popped, so the list can grow past n
3. 3. In the sliding window median lesson, the values 1, 3 and -1 are added in that order using the two-halves design. Which split is correct?

   lower {1, 3} and upper {-1}lower {-1} and upper {1, 3}lower {1, -1} and upper {3}lower {1} and upper {-1, 3}
4. 4. In the indexed heap, what does pos[id] hold?

   the position of item id in the heap, or -1 if it is not in the heapthe key of item idthe id of the item at heap position idthe parent of item id
5. 5. What does this print? ``python from collections import Counter delayed = Counter() delayed[5] += 1 delayed[5] += 1 delayed[9] += 1 print(delayed[5], delayed[9], 7 in delayed) ``

   1 1 False2 1 True2 1 False2 0 False