Relaxed Heaps: An Alternative to Fibonacci Heaps,

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1987
Accession Number
ADA194030

Entities

People

  • Harold N. Gabow
  • James R. Driscoll
  • Robert Tarjan
  • Ruth Shrairman

Organizations

  • Princeton University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Binomials
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Sequences
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.