# Strict Fibonacci Heaps

In * Proc. 44th Annual ACM Symposium on Theory of Computing*, pages 1177-1184, 2012.

## Abstract

We present the first pointer-based heap implementation with time
bounds matching those of Fibonacci heaps in the worst case. We
support make-heap, insert, find-min, meld and decrease-key in
worst-case *O*(1) time, and delete and delete-min in worst-case
*O*(lg *n*) time, where *n* is the size of the heap. The data
structure uses linear space.

A previous, very complicated, solution achieving the same time bounds
in the RAM model made essential use of arrays and extensive use of
redundant counter schemes to maintain balance. Our solution uses
neither. Our key simplification is to discard the structure of the
smaller heap when doing a meld. We use the pigeonhole principle in
place of the redundant counter mechanism.

**Copyright notice**
Copyright © 2012 by the Association for Computer Machinery, Inc.

**Online version**

stoc12.pdf (166 Kb)

**DOI**

10.1145/2213977.2214082

**Note**
Video of conference talk available at the papers DOI (see "Source Materials")

**Slides**

stoc12.pdf (316 Kb), stoc12.pptx (233 Kb)

**BIBT**_{E}X entry

@inproceedings{stoc12,
author = "Gerth St{\o}lting Brodal and George Lagogiannis and Robert E. Tarjan",
booktitle = "Proc. 44th Annual ACM Symposium on Theory of Computing",
doi = "10.1145/2213977.2214082",
isbn = "978-1-4503-1245-5",
pages = "1177-1184",
title = "Strict Fibonacci Heaps",
year = "2012"
}

l>