A transformation, referred to as depletion, is defined for comparison-based data structures that implement priority queue operations. The depletion transform yields a representation of the data structure as a forest of heap-ordered trees. Under certain circumstances this transform can result in a useful alternative to the original data structure. As an application, we introduce a new variation of skew-heaps that efficiently implements decrease-key operations. Additionally, we construct a new version of the pairing heap data structure that experimentally exhibits improved efficiency
['Michael L. Fredman']
A Priority Queue Transform