Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99616
Title: Worst case performance of an algorithm for generating Huffman codes
Authors: Ong, Ghim Hwee 
Issue Date: 1994
Source: Ong, Ghim Hwee (1994). Worst case performance of an algorithm for generating Huffman codes. National Conference Publication - Institution of Engineers, Australia 2 (94 /9) : 1165-1169. ScholarBank@NUS Repository.
Abstract: This paper presents an algorithm for generating n Huffman codes with a worst case of (2n log2n+2.172026n) comparisons. The algorithm is based on the worst case result of a weak-heap data structure for sorting. The idea of weak-heap sorting is incorporated into the Huffman tree building process in the proposed algorithm. The primary objective of this paper is not to devise a new method for generating Huffman codes, but to analyze how effectively the weak-heap data structure can be adapted to the Huffman tree building process. The performance of the algorithm in execution time is evaluated with a list of ordered, random, and reverse ordered data containing from 5,000 to 200,000 items. It is shown that the algorithm is most efficient when given a set of reverse ordered data.
Source Title: National Conference Publication - Institution of Engineers, Australia
URI: http://scholarbank.nus.edu.sg/handle/10635/99616
ISSN: 03136922
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

28
checked on Feb 23, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.