O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 OperationsAmortized 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required