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