Preserving order in a forest in less than logarithmic time
- 1 October 1975
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We present a data structure, based upon a stratified binary tree, which enables us to manipulate on-line a priority queue whose priorities are selected from the interval 1...n, with an average and worst case processing time of O(log log n) per instruction. The structure is used to obtain a mergeable heap whose time requirements are about as good.Keywords
This publication has 5 references indexed in Scilit:
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- Efficient Generation of Optimal Prefix CodeJournal of the ACM, 1975
- PASCAL User Manual and ReportLecture Notes in Computer Science, 1974
- Set Merging AlgorithmsSIAM Journal on Computing, 1973
- On finding lowest common ancestors in treesPublished by Association for Computing Machinery (ACM) ,1973