Accession Number : ADA194030

Title :   Relaxed Heaps: An Alternative to Fibonacci Heaps,

Corporate Author : PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE

Personal Author(s) : Driscoll, James R ; Gabow, Harold N ; Shrairman, Ruth ; Tarjan, Robert E

PDF Url : ADA194030

Report Date : Jul 1987

Pagination or Media Count : 17

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.

Descriptors :   *QUEUEING THEORY, *BINOMIALS, TREES, NODES, SEQUENCES

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE