What is Huffman’s algorithm?

Question

Assume priority queue in Dijkstra’s algorithm is implemented using a sorted link list and graph G (V, E) is represented using adjacency matrix.

What is the time complexity of Dijkstra’s algorithm (Assume graph is connected)?

Answer 1

It is designed for compressing (longer) texts, mapping the characters involved to bitfields of various length. Suppose that the frequency of each character is given [or one can also derive it from the given text as (occurrences of char) / (full text)].

Then the algorithm creates the mapping so that
- the more frequent characters get smaller bitfields
- each assigned bitfield is uniquely recognizable if concatenated (that's how the binary trees enter the picture).

For details and examples, you can start e.g. from wikipedia or the following video.

Answer 2

Huffman’s algorithm is associated in creating extended binary trees that has minimum weighted path lengths from the given weights. It makes use of a table that contains frequency of occurrence for each data element.

If this Huffman code is used to represent the signal, then the average length is lowered to 1.85 bits/symbol; it is still far from the theoretical limit because the probabilities of the symbols are different from negative powers of two. The technique works by creating a binary tree of nodes.