Worst case performance of an algorithm for generating Huffman codes

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.