Medians and indexed heaps

Questions 1 to 5 of 7

1. 1. An IndexedMinHeap holds n items. What is the Big-O cost of one decrease_key call?

   O(1), because the item is found in pos_ and its priority is changed in placeO(log n), because the item sifts up through at most about log n levelsO(n), because the whole heap array is scanned to find the itemO(n log n), because the heap is rebuilt after the change
2. 2. The two-heap RunningMedian method slides a window of size k across a list of n values. Roughly how many steps does the whole run take?

   n times k times log k, because each window is sorted from scratchn times log n, because the window size does not change the costn times log k, because each insert and erase is a heap push or pop on about k valuesn squared, because both heaps are rebuilt at every step
3. 3. Why does RunningMedian::erase add a count to pending_ instead of removing the value from its heap at once?

   A value that leaves the window must stay in the heap so the median can be recomputed from scratchA count of pending values keeps each heap sorted again after every inserterase must not change lowSize_ or highSize_, so the sizes stay fixedstd::priority_queue cannot remove a value from the middle, so the value is marked and dropped when it reaches a top
4. 4. In IndexedMinHeap, what does the pos_ array store?

   The priority of each id, so two items can be compared in constant timeThe slot number of each id, so decrease_key can find the item without a searchThe ids in heap order, so the top is always at index 0A flag for each id that marks it as popped
5. 5. What does this program print? ``cpp #include <iostream> int main() { int a = 1, b = 2; std::cout << (a + b) / 2 << ' ' << (a + b) / 2.0 << '\n'; } ``

   1 1.51.5 1.52 2.01 1