Loading...
Please wait, while we are loading the content...
Similar Documents
Worst-case efficient external-memory priority queues (1997).
| Content Provider | CiteSeerX |
|---|---|
| Author | Brodal, Gerth Stølting Katajainen, Jyrki |
| Abstract | A priority queue Q is a data structure that maintains a collection of elements, each element having an associated priority drawn from a totally ordered universe, under the operations Insert, which inserts an element into Q, and DeleteMin, which deletes an element with the minimum priority from Q. In this paper a priority-queue implementation is given which is efficient with respect to the number of block transfers or I/Os performed between the internal and external memories of a computer. Let B and M denote the respective capacity of a block and the internal memory measured in elements. The developed data structure handles any intermixed sequence of Insert and DeleteMin operations such that in every disjoint interval of B consecutive priority-queue operations at most c log M=B N M I/Os are performed, for some positive constant c. These I/Os are divided evenly among the operations: if B c log M=B N M , one I/O is necessary for every B=(c log M=B N M )th operation and if B ! c log M... |
| File Format | |
| Publisher Date | 1997-01-01 |
| Access Restriction | Open |
| Subject Keyword | Worst-case Efficient External-memory Priority Queue Data Structure Disjoint Interval Th Operation Ordered Universe Priority-queue Implementation Block Transfer Priority Drawn Developed Data Structure Deletemin Operation Intermixed Sequence Internal Memory Priority Queue Minimum Priority Operation Insert Respective Capacity Positive Constant Consecutive Priority-queue Operation External Memory |
| Content Type | Text |
| Resource Type | Article |
