patternMinor
Priority queue with unique elements and sublinear time merge?
Viewed 0 times
priorityuniqueelementsmergewithtimesublinearandqueue
Problem
Some priority queues, like the height-based leftist tree (or here) support merging in $\mathcal O\left(\log n\right)$ time.
I am looking for a priority queue that merges in (expected|average|amortized|worst-case) sub-linear time, but also has the following properties:
Is this impossible?
I am looking for a priority queue that merges in (expected|average|amortized|worst-case) sub-linear time, but also has the following properties:
- Elements are unique
peekandpopshould work in (expected|average|amortized|worst-case) sub-linear time
Is this impossible?
Solution
Keep your elements in linked lists of buckets. Buckets will have size $O(\lg^2 n)$ when stored in a list with $n$ total elements. Buckets are stored as balanced search trees with $O(\lg n)$ insert (and, since each bucket has size $O(\lg^2 n)$, this is actually $O(\lg \lg n)$), $O(1)$ extractMin, $O(n+m)$ merge, $O(\lg n)$ split, and no duplicates. The liked list should be sorted by the size of the buckets, though not their key values.
To maintain the bucket invariant, we need to occasionally combine or split buckets. To pay for this, we assign each priority queue a potential. This lets us use the physicist's amortization.
Each bucket will be assigned a potential of $0$ if it has size within $1$ of $\lg^2 n$ and a potential of $c \lg^2 n$ if it is size $\lg^2 n/d$ or $d \lg^2 n$ (for constants $c$ and $d$ to be determined later), varying bitonicly and linearly in the size of the bucket.
The tricky method is merge. Assume we are merging two lists of size $n$ and $an$, for $a>1$. We split into two cases depending on whether $a \lg^2 n$, we destroy the smaller priority queue and insert its items one-by-one into the larger queue. As long as insert is $o(\lg^2 n)$ amortized, this is sublinear.
Insert adds an element to the smallest bucket. This increases its potential by at most $O(1)$ and increases the potential of the rest of the buckets by at most $O(\lg^2 (n+1) - \lg^2 n) = O(\lg n/n)$. Since there are $O(n/\lg^2 n)$ buckets, the total increase in potential is $O(1/\lg n)$. If the smallest bucket is large, some splitting may be required, but this is amortized free (paid for by the potential we get back). The total amortized cost of insert is thus the cost to insert it into a bucket, which is $O(\lg \lg n)$.
extractMin traverses the bucket list and identifies the buckets with minimum key. It removes the minimum key from each of these buckets, rearranging the bucket list as necessary to maintain order. The total structure size may change by $O(n/\lg^2 n)$ if we remove a key from each bucket. This induces a potential change of at most $O(\lg n)$ in each bucket, for a total potential change of $O(n/\lg n)$. The traversal and removal take time linear in the number of buckets, which is $o(n)$.
Note that these operations, including an extractMin that extracts every copy of the minimum, are sublinear in the number of elements, not the number of unique elements. The number of unique elements in a priority queue of size $n$ may be as low as $\Theta(\lg^2 n)$.
To maintain the bucket invariant, we need to occasionally combine or split buckets. To pay for this, we assign each priority queue a potential. This lets us use the physicist's amortization.
Each bucket will be assigned a potential of $0$ if it has size within $1$ of $\lg^2 n$ and a potential of $c \lg^2 n$ if it is size $\lg^2 n/d$ or $d \lg^2 n$ (for constants $c$ and $d$ to be determined later), varying bitonicly and linearly in the size of the bucket.
The tricky method is merge. Assume we are merging two lists of size $n$ and $an$, for $a>1$. We split into two cases depending on whether $a \lg^2 n$, we destroy the smaller priority queue and insert its items one-by-one into the larger queue. As long as insert is $o(\lg^2 n)$ amortized, this is sublinear.
Insert adds an element to the smallest bucket. This increases its potential by at most $O(1)$ and increases the potential of the rest of the buckets by at most $O(\lg^2 (n+1) - \lg^2 n) = O(\lg n/n)$. Since there are $O(n/\lg^2 n)$ buckets, the total increase in potential is $O(1/\lg n)$. If the smallest bucket is large, some splitting may be required, but this is amortized free (paid for by the potential we get back). The total amortized cost of insert is thus the cost to insert it into a bucket, which is $O(\lg \lg n)$.
extractMin traverses the bucket list and identifies the buckets with minimum key. It removes the minimum key from each of these buckets, rearranging the bucket list as necessary to maintain order. The total structure size may change by $O(n/\lg^2 n)$ if we remove a key from each bucket. This induces a potential change of at most $O(\lg n)$ in each bucket, for a total potential change of $O(n/\lg n)$. The traversal and removal take time linear in the number of buckets, which is $o(n)$.
Note that these operations, including an extractMin that extracts every copy of the minimum, are sublinear in the number of elements, not the number of unique elements. The number of unique elements in a priority queue of size $n$ may be as low as $\Theta(\lg^2 n)$.
Context
StackExchange Computer Science Q#16611, answer score: 4
Revisions (0)
No revisions yet.