Weight Biased Leftist Trees and Modified Skip Lists
this paper, we are concerned primarily with the insert and delete min operations. The different data structures that have been proposed for the representation of a priority queue differ in terms of the performance guarantees they provide. Some guarantee good performance on a per operation basis whil...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Text |
| Language: | English |
| Published: |
1996
|
| Subjects: | |
| Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.2962 http://www.cise.ufl.edu/~sahni/papers/wblt.pdf |
| Summary: | this paper, we are concerned primarily with the insert and delete min operations. The different data structures that have been proposed for the representation of a priority queue differ in terms of the performance guarantees they provide. Some guarantee good performance on a per operation basis while others do this only in the amortized sense. Heaps permit one to delete the min element and insert an arbitrary element into an n element priority queue in O(logn) time per operation; a find min takes O(1) time. Additionally, a heap is an implicit data structure that has no storage overhead associated with it. All other priority queue structures are pointer-based and so require additional storage for the pointers. Leftist trees also support the insert and delete min operations in O(log n) time per operation and the find min operation in O(1) time. Additionally, they permit us to meld pairs of priority queues in logarithmic time |
|---|