ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract Anorder-statistic deque is a deque that also supports the operationfind(k, D), wherefind(k, D) returns the item inD with rankk. Assumingk is fixed, we show how to implement an order-statistic deque so thatinject(x, D), eject(D), push(x, D), andpop(D) take O(logk) amortized time andfind(k, D) takes worst-case constant time; the time bounds can be made worst case using a technique of Gajewska and Tarjan. We also show our implementations are optimal in the algebraic decision tree model of computation. This deque is applied to three problems: computing order-statistic filters, finding a smallest area convex quadrilateral in the plane, and computing “batched” order statistics.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01193574
Permalink
