Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap - a sequence of m decrease-key and n delete-min operations takes time O(m + n log n). A variant of relaxed heaps achieves similar bounds in the worst case - O(1) time for decrease-key and O(log n) for delete-min. A relaxed heap is a type of binomial queue that allows heap order to be violated.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/665

[2] http://www.cs.princeton.edu/research/techreps/author/670

[3] http://www.cs.princeton.edu/research/techreps/author/721

[4] http://www.cs.princeton.edu/research/techreps/author/384

[5] ftp://ftp.cs.princeton.edu/techreports/1987/109.pdf