Please use this identifier to cite or link to this item:
|Title:||Worst case performance of an algorithm for generating Huffman codes|
|Authors:||Ong, Ghim Hwee|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Feb 23, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.