An O(nloglogn) On-line Algorithm for the Insert-Exact Min Problem
| dc.contributor.author | Boas, P. van Emde | en_US |
| dc.date.accessioned | 2007-04-19T19:11:38Z | |
| dc.date.available | 2007-04-19T19:11:38Z | |
| dc.date.issued | 1974-12 | en_US |
| dc.description.abstract | Integers within the range 1,...,n are inserted in a set, and on several occasions the minimal element is extracted from the set. We present an algorithm to executee a sequence of O(n) of these instrucitions on-line in time O(nloglogn) on a Random Access Machine. The instruction repertoire can be extended by instructions like allmin(i) (delete all elements not greater than i), extract max, or predecessor (i) (find the largest element less than i), without disturbing the O(loglogn) processing time per item. Whereas the off-line insert-extract min problem is known to be reducible to the on-line union-find problem, we prove that the off-line insert-allmin problem is equivalent to the off-line union-find problem, hence the off-line problems have faster algorithms. As an application we show that our algorithm can be used to process a sequence of O(n) instructions of the types: "split an interval", "unite two adjacent intervals", and "find the interval currently containing element j", on-line in time O(nloglogn). Keywords: set-manipulation, Analysis of Algorithms, binary tree. | en_US |
| dc.format.extent | 1330596 bytes | |
| dc.format.extent | 470736 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR74-221 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6060 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | An O(nloglogn) On-line Algorithm for the Insert-Exact Min Problem | en_US |
| dc.type | technical report | en_US |