Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues

The authors provide an efficient implementation of catenable mindeques. To prove that the resulting data structure achieves constant amortized time per operation, they consider order preserving path compression. They prove a linear bound on deque ordered spine-only path compression, a case of order persevering path compression employed by the data structure. >

Authors

• Adam L. Buchsbaum
• Rajamani Sundar
• Robert Endre Tarjan

Keywords

• Data structures
• Content addressable storage
• Computer science
• Contracts
• Linearity
• Data Structure
• Path Compression
• Time Constant
• Elements
• Linear Time
• Subtree
• Node Level
• Catenary
• Definition Of Levels
• Minimal Element
• Worst-case Time
• Order Preserving