# Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time

Technical Report, 1505.00147., arXiv.org, 15 pages, May 2015.

## Abstract

The binary heap of Williams (1964) is a simple priority queue
characterized by only storing an array containing the elements and
the number of elements *n* - here denoted a *strictly
implicit* priority queue. We introduce two new strictly implicit
priority queues. The first structure supports amortized *O*(1)
time **Insert** and *O*(log *n*) time **ExtractMin**
operations, where both operations require amortized *O*(1) element
moves. No previous implicit heap with *O*(1) time **Insert**
supports both operations with *O*(1) moves. The second structure
supports worst-case *O*(1) time **Insert** and *O*(log *n*) time
(and moves) **ExtractMin** operations. Previous results were
either amortized or needed *O*(log *n*) bits of additional state
information between operations.

**Online version**
arxiv1505.00147.pdf (337 Kb)

**Links**

**BIBT**_{E}X entry

@techreport{arxiv1505.00147,
author = "Gerth St{\o}lting Brodal and Jesper Sindahl Nielsen and Jakob Truelsen",
institution = "arXiv.org",
month = "May",
number = "1505.00147.",
pages = "15",
title = "Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time",
year = "2015"
}