The Post-Order Heap

Nicholas J. A. Harvey, Kevin C. Zatloukal

PDF (99 KBytes)
PostScript (180 KBytes)
PowerPoint Slides (310 KBytes)
Source Code (5 KBytes)

Priority Queue, Heap, Amortized Analysis, Implicit Data Structure


We propose the post-order heap, a new data structure for implementing priority queues. Our structure is a simple variant of the binary heap that requires only O(1) amortized time for Insert operations and O(log n) time in the worst case for Delete-Min operations. Like the binary heap, the post-order heap is an implicit data structure, meaning that a structure containing n elements can be stored using only the first n locations of an array and O(1) additional words of storage.

To appear at the Third International Conference on Fun with Algorithms (FUN 2004), Elba, Italy, May 2004.