Codarea Huffman este un algoritm de comprimare a datelor fără pierderi. Ideea este de a atribui coduri cu lungime variabilă caracterelor de intrare, lungimile codurilor atribuite se bazează pe frecvențele caracterelor corespunzătoare.
Codurile cu lungime variabilă atribuite caracterelor introduse sunt Coduri de prefix , înseamnă că codurile (secvențele de biți) sunt alocate în așa fel încât codul atribuit unui caracter să nu fie prefixul codului atribuit oricărui alt caracter. Acesta este modul în care Huffman Coding se asigură că nu există ambiguitate atunci când decodează fluxul de biți generat.
Să înțelegem codurile de prefix cu un exemplu de contor. Să fie patru caractere a, b, c și d, iar codurile lor de lungime variabilă corespunzătoare să fie 00, 01, 0 și 1. Această codificare duce la ambiguitate deoarece codul atribuit lui c este prefixul codurilor atribuite lui a și b. Dacă fluxul de biți comprimat este 0001, ieșirea decomprimată poate fi cccd sau ccb sau acd sau ab.
Vedea acest pentru aplicațiile Huffman Coding.
Există în principal două părți majore în Huffman Coding

1. Construiește un arbore Huffman din caracterele introduse.
2. Traversați Arborele Huffman și atribuiți coduri personajelor.

Algoritm:

Metoda care este folosită pentru a construi codul de prefix optim este numită Codare Huffman .

Acest algoritm construiește un arbore de jos în sus. Putem desemna acest copac prin T

Fie, |c| fie numărul de frunze

|c| -1 sunt numărul de operații necesare pentru a îmbina nodurile. Q să fie coada prioritară care poate fi utilizată în timpul construirii unui heap binar.

Algorithm Huffman (c) { n= |c| Q = c for i<-1 to n-1 do { temp <- get node () left (temp] Get_min (Q) right [temp] Get Min (Q) a = left [templ b = right [temp] F [temp]<- f[a] + [b] insert (Q, temp) } return Get_min (0) }>

Pași pentru a construi Arborele Huffman
Intrarea este o serie de caractere unice împreună cu frecvența lor de apariție, iar rezultatul este Arborele Huffman.

1. Creați un nod frunză pentru fiecare caracter unic și construiți o grămadă minimă a tuturor nodurilor frunză (Heap min este utilizat ca coadă prioritară. Valoarea câmpului de frecvență este folosită pentru a compara două noduri în heap min. Inițial, caracterul cel mai puțin frecvent este la rădăcină)
2. Extrageți două noduri cu frecvența minimă din heap-ul min.
   
3. Creați un nou nod intern cu o frecvență egală cu suma frecvențelor celor două noduri. Faceți primul nod extras ca fiul său stâng și celălalt nod extras ca fiul său drept. Adăugați acest nod la heap-ul min.
4. Repetați pașii #2 și #3 până când heap-ul conține un singur nod. Nodul rămas este nodul rădăcină și arborele este complet.
   Să înțelegem algoritmul cu un exemplu:

character Frequency a 5 b 9 c 12 d 13 e 16 f 45>

Pasul 1. Construiți un heap min care conține 6 noduri în care fiecare nod reprezintă rădăcina unui arbore cu un singur nod.
Pasul 2 Extrageți două noduri de frecvență minimă din heap min. Adăugați un nou nod intern cu frecvența 5 + 9 = 14.

Ilustrația pasului 2

Acum min. heap conține 5 noduri, unde 4 noduri sunt rădăcini ale copacilor cu un singur element fiecare, iar un nod heap este rădăcina arborelui cu 3 elemente

character Frequency c 12 d 13 Internal Node 14 e 16 f 45>

Pasul 3: Extrageți două noduri de frecvență minimă din heap. Adăugați un nou nod intern cu frecvența 12 + 13 = 25

Ilustrația pasului 3

Acum, heap min conține 4 noduri, unde 2 noduri sunt rădăcini ale copacilor cu un singur element fiecare, iar două noduri heap sunt rădăcini ale copacului cu mai multe noduri

character Frequency Internal Node 14 e 16 Internal Node 25 f 45>

Pasul 4: Extrageți două noduri de frecvență minimă. Adăugați un nou nod intern cu frecvența 14 + 16 = 30

Ilustrația pasului 4

Acum min heap conține 3 noduri.

character Frequency Internal Node 25 Internal Node 30 f 45>

Pasul 5: Extrageți două noduri de frecvență minimă. Adăugați un nou nod intern cu frecvența 25 + 30 = 55

Ilustrația pasului 5

Acum min heap conține 2 noduri.

character Frequency f 45 Internal Node 55>

Pasul 6: Extrageți două noduri de frecvență minimă. Adăugați un nou nod intern cu frecvența 45 + 55 = 100

Ilustrația pasului 6

Acum min heap conține un singur nod.

seleniu

character Frequency Internal Node 100>

Deoarece heap-ul conține un singur nod, algoritmul se oprește aici.

Pași pentru a imprima coduri din Arborele Huffman:
Traversați arborele format începând de la rădăcină. Mențineți o matrice auxiliară. În timp ce vă deplasați la copilul din stânga, scrieți 0 în matrice. În timp ce vă deplasați la copilul drept, scrieți 1 în matrice. Imprimați matricea când este întâlnit un nod frunză.

Pași pentru a imprima codul din HuffmanTree

Codurile sunt după cum urmează:

character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>

Mai jos este implementarea abordării de mai sus:

C

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C++ program for Huffman Coding> #include> #include> using> namespace> std;> > // This constant can be avoided by explicitly> // calculating height of Huffman Tree> #define MAX_TREE_HT 100> > // A Huffman tree node> struct> MinHeapNode {> > >// One of the input characters> >char> data;> > >// Frequency of the character> >unsigned freq;> > >// Left and right child of this node> >struct> MinHeapNode *left, *right;> };> > // A Min Heap: Collection of> // min-heap (or Huffman tree) nodes> struct> MinHeap {> > >// Current size of min heap> >unsigned size;> > >// capacity of min heap> >unsigned capacity;> > >// Array of minheap node pointers> >struct> MinHeapNode** array;> };> > // A utility function allocate a new> // min heap node with given character> // and frequency of the character> struct> MinHeapNode* newNode(>char> data, unsigned freq)> {> >struct> MinHeapNode* temp = (>struct> MinHeapNode*)>malloc>(> >sizeof>(>struct> MinHeapNode));> > >temp->stânga = temp->dreapta = NULL;>>> temp->date = date;>>> temp->frecvență = frecvență;>>> >return> temp;> }> > // A utility function to create> // a min heap of given capacity> struct> MinHeap* createMinHeap(unsigned capacity)> > {> > >struct> MinHeap* minHeap> >= (>struct> MinHeap*)>malloc>(>sizeof>(>struct> MinHeap));> > >// current size is 0> >minHeap->dimensiune = 0;>>> >minHeap->capacitate = capacitate;>>> >minHeap->matrice = (>struct> MinHeapNode**)>malloc>(> >minHeap->capacitate *>>>(>struct> MinHeapNode*));> >return> minHeap;> }> > // A utility function to> // swap two min heap nodes> void> swapMinHeapNode(>struct> MinHeapNode** a,> >struct> MinHeapNode** b)> > {> > >struct> MinHeapNode* t = *a;> >*a = *b;> >*b = t;> }> > // The standard minHeapify function.> void> minHeapify(>struct> MinHeap* minHeap,>int> idx)> > {> > >int> smallest = idx;> >int> left = 2 * idx + 1;> >int> right = 2 * idx + 2;> > >if> (left size> >&& minHeap->matrice[stânga]->frecvență>>> array[smallest]->frecvență)>>> smallest = left;> > >if> (right size> >&& minHeap->matrice[dreapta]->frecvență>>> array[smallest]->frecvență)>>> smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->matrice[cel mai mic],> >&minHeap->matrice[idx]);>>> minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->dimensiune == 1);>>> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->matrice[0];>>> minHeap->matrice[0] = minHeap->array[minHeap->size - 1];>>> >--minHeap->mărimea;>>> minHeapify(minHeap, 0);> > >return> temp;> }> > // A utility function to insert> // a new node to Min Heap> void> insertMinHeap(>struct> MinHeap* minHeap,> >struct> MinHeapNode* minHeapNode)> > {> > >++minHeap->mărimea;>>> int> i = minHeap->dimensiune - 1;>>> >while> (i> >&& minHeapNode->frecvență>>> array[(i - 1) / 2]->frecvență) {>>> >minHeap->matrice[i] = minHeap->matrice[(i - 1) / 2];>>> i = (i - 1) / 2;> >}> > >minHeap->matrice[i] = minHeapNode;>>> > // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->dimensiune - 1;>>> int> i;> > >for> (i = (n - 1) / 2; i>= 0; --i)>>> minHeapify(minHeap, i);> }> > // A utility function to print an array of size n> void> printArr(>int> arr[],>int> n)> {> >int> i;> >for> (i = 0; i   cout << arr[i];     cout << '
';  }    // Utility function to check if this node is leaf  int isLeaf(struct MinHeapNode* root)    {     return !(root->stânga) && !(rădăcină->dreapta);  } // Creează un heap min de capacitate // egal cu dimensiunea și inserează toate caracterele // date[] în heap min. Inițial, dimensiunea // min heap este egală cu capacitatea struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size);     pentru (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = dimensiune; buildMinHeap(minHeap); return minHeap; } // Funcția principală care construiește Huffman tree struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top // Pasul 1: Creați un heap min de capacitate // egal cu dimensiunea; . Inițial, există // moduri egale cu struct MinHeap* minHeap = createAndBuildMinHeap (data, freq, size // Iterați în timp ce dimensiunea heap-ului nu devine 1 while (!isSizeOne(minHeap)) { //; Pasul 2: Extrageți cele două elemente // frecvență minime din heap min left = extractMin(minHeap right = extractMin(minHeap // Pasul 3: Creați un nou nod // intern cu frecvența // egală cu suma); frecvențele două noduri // Faceți cele două noduri extrase ca // copii stânga și dreapta ai acestui nou nod // Adăugați acest nod în heap-ul min // '$' este o valoare specială pentru nodurile interne, nu //. folosit top = newNode('$', stânga->frecvență + dreapta->frecvență);     sus->stânga = stânga;   sus->dreapta = dreapta;     insertMinHeap(minHeap, sus);   } // Pasul 4: Nodul rămas este // nodul rădăcină și arborele este complet.   returnează extractMin(minHeap);  } // Imprimă coduri Huffman de la rădăcina arborelui Huffman.  // Folosește arr[] pentru a stoca coduri void printCodes(struct MinHeapNode* root, int arr[], int top) { // Atribuiți 0 la marginea stângă și recurgeți dacă (root->left) { arr[top] = 0 ;   printCodes(rădăcină->stânga, arr, sus + 1);   } // Atribuiți 1 la marginea dreaptă și repetați dacă (rădăcină->dreapta) { arr[sus] = 1;   printCodes(rădăcină->dreapta, arr, sus + 1);   } // Dacă acesta este un nod frunză, atunci // conține unul dintre // caracterele de intrare, tipăriți caracterul // și codul său din arr[] if (isLeaf(root)) { cout ': ';   printArr(arr, sus);   } } // Funcția principală care construiește un // Arborele Huffman și tipărirea codurilor prin parcurgerea // Arborele Huffman construit void HuffmanCodes(data char[], frecvența int[], dimensiunea int) { // Construiți structura arborelui Huffman MinHeapNode* root = buildHuffmanTree(date, frecvență, dimensiune);     // Tipăriți codurile Huffman folosind // arborele Huffman construit deasupra int arr[MAX_TREE_HT], top = 0;     printCodes(rădăcină, arr, top);  } // Cod driver int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '};   int frecvență[] = { 5, 9, 12, 13, 16, 45 };     int size = sizeof(arr) / sizeof(arr[0]);     HuffmanCodes(arr, frecvență, dimensiune);     întoarce 0;  }>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C++(STL) program for Huffman Coding with STL> #include> using> namespace> std;> > // A Huffman tree node> struct> MinHeapNode {> > >// One of the input characters> >char> data;> > >// Frequency of the character> >unsigned freq;> > >// Left and right child> >MinHeapNode *left, *right;> > >MinHeapNode(>char> data, unsigned freq)> > >{> > >left = right = NULL;> >this>->date = date;>>> this>->frecvență = frecvență;>>> }> };> > // For comparison of> // two heap nodes (needed in min heap)> struct> compare {> > >bool> operator()(MinHeapNode* l, MinHeapNode* r)> > >{> >return> (l->frecvență> r->frecvență);>>> }> };> > // Prints huffman codes from> // the root of Huffman Tree.> void> printCodes(>struct> MinHeapNode* root, string str)> {> > >if> (!root)> >return>;> > >if> (root->date !=>'$'>)> >cout ': ' << str << '
';     printCodes(root->stânga, str + '0');   printCodes(rădăcină->dreapta, str + '1');  } // Funcția principală care construiește un arbore Huffman și // imprimă coduri prin parcurgerea arborelui Huffman construit void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top;     // Creați un heap min și inserează toate caracterele de date[] priority_queue compare> minHeap;     pentru (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Repetați în timp ce dimensiunea heap-ului nu devine 1 în timp ce (minHeap.size() != 1 ) { // Extrage cele două elemente frecvențe minime din minHeap.top(); minHeap.pop(); cu // frecvență egală cu suma // frecvențele a două noduri. Faceți // două noduri extrase ca copii din stânga și dreapta // a acestui nod // Adăugați acest nod // la heap-ul minim '$' o valoare specială // pentru nodurile interne, nu este folosit top = new MinHeapNode('$', left->freq + right->left = left top->right = right; (sus); } // Imprimați codurile Huffman folosind // arborele Huffman construit deasupra printCodes(minHeap.top(), '' } // Driver Code int main() { char arr[] = { '); a', 'b', 'c', 'd', 'e', 'f' } int frec[] = { 5, 9, 12, 13, 16 , 45 }; int size = sizeof(arr) / sizeof(arr[0]);     întoarce 0;  } // Acest cod este contribuit de Aditya Goel>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
șir de caractere în java
 
 
 
 
 import> java.util.Comparator;> import> java.util.PriorityQueue;> import> java.util.Scanner;> > class> Huffman {> > >// recursive function to print the> >// huffman-code through the tree traversal.> >// Here s is the huffman - code generated.> >public> static> void> printCode(HuffmanNode root, String s)> >{> > >// base case; if the left and right are null> >// then its a leaf node and we print> >// the code s generated by traversing the tree.> >if> (root.left ==>null> && root.right ==>null> >&& Character.isLetter(root.c)) {> > >// c is the character in the node> >System.out.println(root.c +>':'> + s);> > >return>;> >}> > >// if we go to left then add '0' to the code.> >// if we go to the right add'1' to the code.> > >// recursive calls for left and> >// right sub-tree of the generated tree.> >printCode(root.left, s +>'0'>);> >printCode(root.right, s +>'1'>);> >}> > >// main function> >public> static> void> main(String[] args)> >{> > >Scanner s =>new> Scanner(System.in);> > >// number of characters.> >int> n =>6>;> >char>[] charArray = {>'a'>,>'b'>,>'c'>,>'d'>,>'e'>,>'f'> };> >int>[] charfreq = {>5>,>9>,>12>,>13>,>16>,>45> };> > >// creating a priority queue q.> >// makes a min-priority queue(min-heap).> >PriorityQueue q> >=>new> PriorityQueue(> >n,>new> MyComparator());> > >for> (>int> i =>0>; i     // creating a Huffman node object   // and add it to the priority queue.   HuffmanNode hn = new HuffmanNode();     hn.c = charArray[i];   hn.data = charfreq[i];     hn.left = null;   hn.right = null;     // add functions adds   // the huffman node to the queue.   q.add(hn);   }     // create a root node   HuffmanNode root = null;     // Here we will extract the two minimum value   // from the heap each time until   // its size reduces to 1, extract until   // all the nodes are extracted.   while (q.size()>1) { // primul minut extras.   HuffmanNode x = q.peek();   q.poll();     // al doilea minut extract.   HuffmanNode y = q.peek();   q.poll();     // nod nou f care este egal HuffmanNode f = nou HuffmanNode();     // la suma frecvenței celor două noduri // atribuirea de valori nodului f.   f.data = x.data + y.data;   f.c = '-';     // primul nod extras ca copil stâng.   f.stânga = x;     // al doilea nod extras ca copil potrivit.   f.dreapta = y;     // marcând nodul f ca nod rădăcină.   rădăcină = f;     // adăugați acest nod la coada de prioritate.   q.adăugați(f);   } // imprimă codurile parcurgând arborele printCode(rădăcină, '');   } } // clasa de noduri este structura de bază // a fiecărui nod prezent în arborele Huffman.  clasa HuffmanNode { int date;   char c;     HuffmanNode a plecat;   HuffmanNode dreapta;  } // clasa comparatoare ajută la compararea nodului // pe baza unuia dintre atributele acestuia.  // Aici vom fi comparați // pe baza valorilor de date ale nodurilor.  clasa MyComparator implementează Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data;   } } // Acest cod este contribuit de Kunwar Desh Deepak Singh>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
strsep
 
 
 
 
 
 # A Huffman Tree Node> import> heapq> > > class> node:> >def> __init__(>self>, freq, symbol, left>=>None>, right>=>None>):> ># frequency of symbol> >self>.freq>=> freq> > ># symbol name (character)> >self>.symbol>=> symbol> > ># node left of current node> >self>.left>=> left> > ># node right of current node> >self>.right>=> right> > ># tree direction (0/1)> >self>.huff>=> ''> > >def> __lt__(>self>, nxt):> >return> self>.freq      # utility function to print huffman  # codes for all symbols in the newly  # created Huffman tree  def printNodes(node, val=''):     # huffman code for current node   newVal = val + str(node.huff)     # if node is not an edge node   # then traverse inside it   if(node.left):   printNodes(node.left, newVal)   if(node.right):   printNodes(node.right, newVal)     # if node is edge node then   # display its huffman code   if(not node.left and not node.right):   print(f'{node.symbol} ->{newVal}') # caractere pentru caracterele arborelui Huffman = ['a', 'b', 'c', 'd', 'e', 'f'] # frecvența caracterelor frecvența = [5, 9, 12, 13, 16, 45] # listă care conține noduri neutilizate noduri = [] # conversia caracterelor și frecvențele # în noduri arborele huffman pentru x în interval(len(chars)): heapq .heappush(noduri, nod(frecvență[x], caractere[x])) în timp ce len(noduri)> 1: # sortează toate nodurile în ordine crescătoare # pe baza frecvenței lor stânga = heapq.heappop(noduri) dreapta = heapq .heappop(noduri) # atribuiți o valoare direcțională acestor noduri left.huff = 0 right.huff = 1 # combinați cele mai mici 2 noduri pentru a crea # nod nou ca părinte newNode = node(left.freq+right.freq, stânga. simbol+right.symbol, stânga, dreapta) heapq.heappush(noduri, newNode) # Arborele Huffman este gata!  printNodes(noduri[0])>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > > // node class is the basic structure> // of each node present in the Huffman - tree.> class HuffmanNode> {> >constructor()> >{> >this>.data = 0;> >this>.c =>''>;> >this>.left =>this>.right =>null>;> >}> }> > // recursive function to print the> >// huffman-code through the tree traversal.> >// Here s is the huffman - code generated.> >function> printCode(root,s)> >{> >// base case; if the left and right are null> >// then its a leaf node and we print> >// the code s generated by traversing the tree.> >if> (root.left ==>null> >&& root.right ==>null> >&& (root.c).toLowerCase() != (root.c).toUpperCase()) {> > >// c is the character in the node> >document.write(root.c +>':'> + s+>' '>);> > >return>;> >}> > >// if we go to left then add '0' to the code.> >// if we go to the right add'1' to the code.> > >// recursive calls for left and> >// right sub-tree of the generated tree.> >printCode(root.left, s +>'0'>);> >printCode(root.right, s +>'1'>);> >}> > >// main function> // number of characters.> >let n = 6;> >let charArray = [>'a'>,>'b'>,>'c'>,>'d'>,>'e'>,>'f'> ];> >let charfreq = [ 5, 9, 12, 13, 16, 45 ];> > >// creating a priority queue q.> >// makes a min-priority queue(min-heap).> >let q = [];> > >for> (let i = 0; i     // creating a Huffman node object   // and add it to the priority queue.   let hn = new HuffmanNode();     hn.c = charArray[i];   hn.data = charfreq[i];     hn.left = null;   hn.right = null;     // add functions adds   // the huffman node to the queue.   q.push(hn);   }     // create a root node   let root = null;   q.sort(function(a,b){return a.data-b.data;});     // Here we will extract the two minimum value   // from the heap each time until   // its size reduces to 1, extract until   // all the nodes are extracted.   while (q.length>1) { // primul minut extras.   fie x = q[0];   q.shift();     // al doilea minut extract.   fie y = q[0];   q.shift();     // nou nod f care este egal fie f = new HuffmanNode();     // la suma frecvenței celor două noduri // atribuirea de valori nodului f.   f.data = x.data + y.data;   f.c = '-';     // primul nod extras ca copil stâng.   f.stânga = x;     // al doilea nod extras ca copil potrivit.   f.dreapta = y;     // marcând nodul f ca nod rădăcină.   rădăcină = f;     // adăugați acest nod la coada de prioritate.   q.push(f);   q.sort(funcția(a,b){return a.data-b.data;});   } // imprimă codurile parcurgând arborele printCode(rădăcină, '');    // Acest cod este contribuit de avanitrachhadiya2155>
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C# program for the above approach> > using> System;> using> System.Collections.Generic;> > // A Huffman tree node> public> class> MinHeapNode> {> >// One of the input characters> >public> char> data;> > >// Frequency of the character> >public> uint> freq;> > >// Left and right child> >public> MinHeapNode left, right;> > >public> MinHeapNode(>char> data,>uint> freq)> >{> >left = right =>null>;> >this>.data = data;> >this>.freq = freq;> >}> }> > // For comparison of two heap nodes (needed in min heap)> public> class> CompareMinHeapNode : IComparer> {> >public> int> Compare(MinHeapNode x, MinHeapNode y)> >{> >return> x.freq.CompareTo(y.freq);> >}> }> > class> Program> {> >// Prints huffman codes from the root of Huffman Tree.> >static> void> printCodes(MinHeapNode root,>string> str)> >{> >if> (root ==>null>)> >return>;> > >if> (root.data !=>'$'>)> >Console.WriteLine(root.data +>': '> + str);> > >printCodes(root.left, str +>'0'>);> >printCodes(root.right, str +>'1'>);> >}> > >// The main function that builds a Huffman Tree and> >// print codes by traversing the built Huffman Tree> >static> void> HuffmanCodes(>char>[] data,>uint>[] freq,>int> size)> >{> >MinHeapNode left, right, top;> > >// Create a min heap & inserts all characters of data[]> >var> minHeap =>new> SortedSet(>new> CompareMinHeapNode());> > >for> (>int> i = 0; i   minHeap.Add(new MinHeapNode(data[i], freq[i]));     // Iterate while size of heap doesn't become 1   while (minHeap.Count != 1)   {   // Extract the two minimum freq items from min heap   left = minHeap.Min;   minHeap.Remove(left);     right = minHeap.Min;   minHeap.Remove(right);     // Create a new internal node with frequency equal to the sum of the two nodes frequencies.   // Make the two extracted node as left and right children of this new node.   // Add this node to the min heap '$' is a special value for internal nodes, not used.   top = new MinHeapNode('$', left.freq + right.freq);     top.left = left;   top.right = right;     minHeap.Add(top);   }     // Print Huffman codes using the Huffman tree built above   printCodes(minHeap.Min, '');   }     // Driver Code   static void Main()   {   char[] arr = { 'a', 'b', 'c', 'd', 'e', 'f' };   uint[] freq = { 5, 9, 12, 13, 16, 45 };     int size = arr.Length;     HuffmanCodes(arr, freq, size);   }  }    // This code is contributed by sdeadityasharma>
 
 
 
 
    
 
>
 
    
 
>
 
  Ieșire  
 
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
 
  Complexitatea timpului: O(nlogn) unde n este numărul de caractere unice. Dacă există n noduri, extractMin() este numit de 2*(n – 1) ori. extractMin() ia timp O(logn) când apelează minHeapify(). Deci, complexitatea generală este O(nlogn). 
Dacă matricea de intrare este sortată, există un algoritm de timp liniar. În curând vom discuta despre asta în următoarea noastră postare.
 
  Complexitatea spațiului:- O(N)  
 
Aplicații ale codării Huffman:
 
 
Acestea sunt utilizate pentru transmiterea de fax și text.
 
Sunt utilizate de formatele convenționale de compresie precum PKZIP, GZIP etc.
 
Codecurile multimedia precum JPEG, PNG și MP3 utilizează codificarea Huffman (pentru a fi mai precis codurile de prefix).
 
 
Este util în cazurile în care există o serie de caractere care apar frecvent.
 
    Referinţă:     
  http://en.wikipedia.org/wiki/Huffman_coding   
Acest articol este compilat de Aashish Barnwal și revizuit de echipa techcodeview.com.