Handbook of Data Structures and Applications, 2nd Edition

6

Skew Heaps^*

C. Pandu Rangan

Indian Institute of Technology, Madras

6.1Introduction

6.2Basics of Amortized Analysis

6.3Meldable Priority Queues and Skew Heaps

Meldable Priority Queue Operations•Amortized Cost of Meld Operation

6.4Bibliographic Remarks

References

6.1Introduction

Priority Queue is one of the most extensively studied Abstract Data Types (ADT) due to its fundamental importance in the context of resource managing systems, such as operating systems. Priority Queues work on finite subsets of a totally ordered universal set U. Without any loss of generality we assume that U is simply the set of all non-negative integers. In its simplest form, a Priority Queue supports two operations, namely,

•insert(x, S): update S by adding an arbitrary ...