  We analyze priority queues of Fibonacci family. The paper is inspired by
Violation heap [1], where A. Elmasry saves one pointer in representation of
Fibonacci heap nodes while achieving the same amortized bounds as Fibonacci
heaps [2] of M. L. Fredman and R. E. Tarjan. Unfortunately author forces the
heaps to be wide, what goes against optimal heap principles. Our goal is to
achieve the same result, but with much narrower heaps. We follow the principle
of superexpensive comparison so we try to remember results of all comparisons
and never compare elements that cannot be minimal. We delay comparisons as long
as possible. Actually I have always want to share superexpensive comparison
principle ideas, discovery of Padovan heaps allowed me to do so. Of course
saving one pointer is not that big goal, but I hope the presented reasoning and
amortized analysis of the resulting heaps is worth a publication.

Data Structures and Algorithms