Time complexity of a 2-heap question

Question

The problem statement is pretty straightforward: given an array of integers and a window size, return an array of doubles of the median of each window.

$arr = 1, 3, 5, 10, 6, 9, 2$ and $k = 3$ would yield a result of $3, 5, 6, 9, 6$.

Using std::priority_queue (in C++) for the heap implementation, there's a minHeap and maxHeap. In a single iteration, insert the value entering our window in the correct heap, rebalance as necessary, add the median to the result (if the window is big enough), then remove the value which is leaving the window from whatever heap it's in: This could require moving all but 1 heap element to the other heap, then moving them back.

The lesson I saw this on actually inherits from priority queue and implements remove functionality: Linear search [O(k)], then removes the item [O(log k)]. It claims O(n * k) complexity as at each iteration the insertion is O(log k) and the search to remove is O(k). I assume in an interview extending a heap beyond it's traditional form is not only unnecessary but probably frowned upon.

I'm curious of the complexity at which the version w/o the direct removal would run. The O(n) part is obvious but the sub operations not as clear to me. A heap will generally have k/2 items in it. In the worst case you delete [O(log k)] and then insert [O(1)] each one. My mind is telling me O(n * k log k) but I wouldn't bet my house on it.

For the record: Not looking for an optimal solution - just the runtime of this one.

Insertion Algorithm: We accept an integer n as input.

1. If n is smaller than the top element of maxHeap, push it on maxHeap and go to step 3.
2. Push n on minHeap.
3. If maxHeap's size is 2 or more than minHeap's size, move the top element of maxHeap to minHeap and go to step 5.
4. If minHeap's size exceeds maxHeap's size, move the top element of minHeap to maxHeap.
5. Stop the algorithm.

Obtaining The Median:

1. If sizes of minHeap and maxHeap are the same, then return the arithmetic mean of their top elements and go to step 4.
2. If maxHeap's size exceeds minHeap's size, return the top element of maxHeap and go to step 4.
3. If minHeap's size exceeds maxHeap, return the top element of minHeap.
4. Stop the algorithm.

Removal Algorithm: We accept an integer n as input.

1. If num is not greater than the top element of maxHeap, remove the current top element from maxHeap and insert it to minHeap, until n becomes the new top element of maxHeap. Else skip to step 4.
2. Remove the top element of maxHeap.
3. Remove the current top element of minHeap and insert it to maxHeap, until the sizes of minHeap and maxHeap will differ by no more than 1. Go to step 7.
4. Remove the current top element from minHeap and insert it to maxHeap, until n becomes the new top element of minHeap.
5. Remove the top element of minHeap.
6. Remove the current top element of maxHeap and insert it to minHeap, until the sizes of minHeap and maxHeap will differ by no more than 1.
7. Stop the algorithm.

Finding Sliding Window Median: We accept an array of integers arr, and an integer k as input.

1. Set left to $0$. Set right to $0$. Set result to $0$.
2. Insert (by using Insertion Algorithm above) the element of arr with index right.
3. If k-1 is not greater than right, add median (found by Obtaining The Median algorithm above) to result. Else go to step 6.
4. Remove the element of arr with index left.
5. Add $1$ to left.
6. If right is less than the greatest index of arr, add $1$ to right and go to step 2.
7. Return the current value of result and stop the algorithm.

This last algorithm is where the mystery is. Worst case we have is to remove a number at the bottom of a $k/2$ sized heap. Would that be $\log k$ for $k/2$ operations then $O(1)$ for $k/2-1$ operations?

Answer 1

It’s easier to figure out if k is large, say k = 100.

You start by creating two heaps with 50 elements each, one with the 50 smallest of the first 100 numbers with fast access to the largest one, and one with the 50 largest, with fast access to the smallest one. The median of all 100 items can be found in O(1).

Now you move the window by one position. Element #0 is removed from its heap, element #100 is added to its heap. Then if you are lucky you have two heaps of size 50, if you are unlucky you have one heap of size 49 and one of size 51, and move either the largest of the small numbers, or the smallest of the large numbers, from its heap to the other heap.

For odd k both heaps need a size that is different by one and the heap with the largest number of elements contains the median. For example k=99, your two heaps must contain 49 and 50 elements. If you are unlucky moving the window results in 48 and 51 items and you move one item over.

Since accessing the second element is also quite fast, you can allow a slightly larger size difference of the heaps which may save some insertions.

And you need O(n log k) operations.

PS. Figured out that you can’t delete an arbitrary item from a heap. So you need to keep track of where your k elements in the window are in the heap, but that doesn’t make things much harder. Still O(n log k).

Answer 2

Store the window in a self-balancing binary search tree, augmented in the standard way for computing item ranks (each node is augmented with the number of values stored in the subtree rooted at that node).

Each time a value arrives, add it to the tree, remove the one leaving the window, compute the median, and output it. Each of those operations can be done in $O(\log k)$ time. (For instance, insert and delete take $O(\log k)$ time, because it is a self-balancing binary tree; finding the median of the values in the tree can be done in $O(\log k)$ time using the augmented rank information.) Therefore, the total running time to process $n$ items will be $O(n \log k)$.