DocumentCode
1311728
Title
Optimal algorithms for inserting a random element into a random heap
Author
Hwang, Hsien-Kuei
Author_Institution
Inst. of Stat. Sci., Acad. Sinica, Taipei, Taiwan
Volume
43
Issue
2
fYear
1997
fDate
3/1/1997 12:00:00 AM
Firstpage
784
Lastpage
787
Abstract
Two algorithms for inserting a random element into a random heap are shown to be optimal (in the sense that they use the least number of comparisons on the average among all comparison-based algorithms) for different values of n under a uniform model
Keywords
Huffman codes; probability; random processes; source coding; tree data structures; Huffman coding tree; comparison-based algorithms; data structure; optimal algorithms; random element insertion; random heap; source coding; Algorithm design and analysis; Binary trees; Data structures; Huffman coding; Job design; Merging; Probability; Processor scheduling; Scheduling algorithm; Sorting;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/18.556140
Filename
556140
Link To Document