Consider a queue of elements with weights $w_0, w_1 \ldots, w_{n-1}$. The queue supports two operations:

  1. Inserting one element at the back of the queue
  2. Reducing the weight of one element in the queue
  3. Given a value $W$, remove from the front of the queue the smallest prefix $w_0, \ldots w_{k-1}$ with total weight $\sum_{i=0}^{k-1} w_i \geq W$.

Operations on the queue must be at most $\mathcal{O}(\log n)$ in the worst-case scenario (no randomized algorithm).

One approach that works is to represent the queue as a self-balancing binary tree such as an AVL, using the insertion order as the key and maintaining the total weight to the left of every node and to the right of every node. While this works, it seems a little bit overkill as we never really make use of the general insertion capability of the AVL... here, we only need insertions at the back.

Another possible structure would be a forest of $v$ complete binary trees where $v$ is the number of 1's in the binary expansion of $n$. The forest would basically match the binary representation of $n$. Adding to the back sometimes creates new trees, and sometimes leads to the merging of trees by "carrying the 1". However, some of that structure is lost when prefixes are being extracted, though perhaps it is salvageable.

Are there other structures I should be thinking about which solve this issue?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.