Huffman Algorithm For Data Structure

Huffman’s Algorithm For Implementation Data-Structure

Main Operations:

1. Choosing the two nodes along with minimal connected probabilities (and making a parent node, etc).
   • Use heap data-structure with this component.
   • This is done N-1times; total work for this component is actually O(N. log N).
2. Addition of every parent node as well as connecting with the children requires a constant time for each node.
   • A total of N-1parent nodes tend to be added, as well as total time with this ‘O(N)’.

Complexity: O(N.log N)

Huffman Code Data Structures

• Binary (Huffman) tree
  • Represents Huffman code
  • Edge->code (‘0’ or ‘1’)
  • Leaf->symbol
  • Path to leaf->encoding
  • Example,

• Priority-queue
  • To efficiently build binary tree.