Double-Ended Priority Queues
Sartaj K. Sahni · 2018
University of Florida 8.1 Definition and an Application . . . . . . . . . . . . . . . . . . . . 8-1 8.2 Symmetric Min-Max Heaps . . . . . . . . . . . . . . . . . . . . . . . 8-2 8.3 Interval Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8-5 Inserting an Element • Removing the Min Element • Initializing an Interval Heap • Complexity of Interval Heap Operations • The Complementary Range Search Problem 8.4 Min-Max Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8-11 Inserting an Element • Removing the Min Element 8.5 Deaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8-16 Inserting an Element • Removing the Min Element 8.6 Generic Methods for DEPQs . . . . . . . . . . . . . . . . . . . . . 8-19 Dual Priority Queues • Total Correspondence • Leaf Correspondence 8.7 Meldable DEPQs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8-21