La codificació Huffman és un algorisme de compressió de dades sense pèrdues. La idea és assignar codis de longitud variable als caràcters d'entrada, les longituds dels codis assignats es basen en les freqüències dels caràcters corresponents.
Els codis de longitud variable assignats als caràcters d'entrada són Codis de prefix , significa que els codis (seqüències de bits) s'assignen de tal manera que el codi assignat a un caràcter no és el prefix del codi assignat a cap altre caràcter. Així és com Huffman Coding s'assegura que no hi hagi ambigüitat en descodificar el flux de bits generat.
Entenem els codis de prefix amb un exemple de comptador. Sigui quatre caràcters a, b, c i d, i els seus codis de longitud variable corresponents siguin 00, 01, 0 i 1. Aquesta codificació condueix a l'ambigüitat perquè el codi assignat a c és el prefix dels codis assignats a a i b. Si el flux de bits comprimit és 0001, la sortida descomprimida pot ser cccd o ccb o acd o ab.
Vegeu això per a aplicacions de Huffman Coding.
Hi ha principalment dues parts principals a Huffman Coding

1. Construeix un arbre Huffman a partir de caràcters d'entrada.
2. Travessa l'arbre de Huffman i assigna codis als personatges.

Algorisme:

S'anomena el mètode que s'utilitza per construir el codi de prefix òptim Codificació Huffman .

Aquest algorisme construeix un arbre de manera inferior a dalt. Podem designar aquest arbre amb T

Deixar, |c| ser nombre de fulles

|c| -1 és el nombre d'operacions necessàries per combinar els nodes. Q serà la cua de prioritat que es pot utilitzar mentre es construeix un munt binari.

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) }>

Passos per construir l'arbre de Huffman
L'entrada és una matriu de caràcters únics juntament amb la seva freqüència d'ocurrències i la sortida és l'arbre de Huffman.

1. Creeu un node full per a cada caràcter únic i creeu un munt mínim de tots els nodes full (Mín munt s'utilitza com a cua de prioritat. El valor del camp de freqüència s'utilitza per comparar dos nodes en munt mínim. Inicialment, el caràcter menys freqüent és a arrel)
2. Extraieu dos nodes amb la freqüència mínima del munt mínim.
   
3. Creeu un nou node intern amb una freqüència igual a la suma de les freqüències dels dos nodes. Feu que el primer node extret sigui el seu fill esquerre i l'altre node extret com el seu fill dret. Afegiu aquest node al munt mínim.
4. Repetiu els passos 2 i 3 fins que la pila contingui només un node. El node restant és el node arrel i l'arbre està complet.
   Entenem l'algorisme amb un exemple:

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

Pas 1. Creeu un munt mínim que contingui 6 nodes on cada node representi l'arrel d'un arbre amb un sol node.
Pas 2 Extreu dos nodes de freqüència mínima de l'heap min. Afegiu un nou node intern amb freqüència 5 + 9 = 14.

Il·lustració del pas 2

Ara el munt mínim conté 5 nodes on 4 nodes són arrels d'arbres amb un sol element cadascun, i un node del munt és arrel d'arbre amb 3 elements.

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

Pas 3: Extreu dos nodes de freqüència mínima de la pila. Afegiu un nou node intern amb freqüència 12 + 13 = 25

Il·lustració del pas 3

Ara min munt conté 4 nodes on 2 nodes són arrels d'arbres amb un sol element cadascun, i dos nodes de munt són arrel d'arbre amb més d'un nodes

Com comprovar la mida de la pantalla del monitor

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

Pas 4: Extraieu dos nodes de freqüència mínima. Afegiu un nou node intern amb freqüència 14 + 16 = 30

Il·lustració del pas 4

Ara min munt conté 3 nodes.

character Frequency Internal Node 25 Internal Node 30 f 45>

Pas 5: Extraieu dos nodes de freqüència mínima. Afegiu un nou node intern amb freqüència 25 + 30 = 55

Il·lustració del pas 5

Ara min munt conté 2 nodes.

character Frequency f 45 Internal Node 55>

Pas 6: Extraieu dos nodes de freqüència mínima. Afegiu un nou node intern amb freqüència 45 + 55 = 100

Il·lustració del pas 6

Ara min munt només conté un node.

character Frequency Internal Node 100>

Com que el munt només conté un node, l'algorisme s'atura aquí.

Passos per imprimir codis de Huffman Tree:
Travessa l'arbre format a partir de l'arrel. Mantenir una matriu auxiliar. Mentre us moveu al fill esquerre, escriviu 0 a la matriu. Mentre us moveu al fill dret, escriviu 1 a la matriu. Imprimiu la matriu quan es trobi un node fulla.

Passos per imprimir codi de HuffmanTree

Els codis són els següents:

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

A continuació es mostra la implementació de l'enfocament anterior:

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->esquerra = temp->dreta = NULL;>>> temp->dades = dades;>>> temp->freqüència = freqüència;>>> >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->mida = 0;>>> >minHeap->capacitat = capacitat;>>> >minHeap->matriu = (>struct> MinHeapNode**)>malloc>(> >minHeap->capacitat *>>>(>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->matriu[esquerra]->freq>>> array[smallest]->freqüència)>>> smallest = left;> > >if> (right size> >&& minHeap->matriu[dreta]->freqüència>>> array[smallest]->freqüència)>>> smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->matriu[més petita],>>> &minHeap->matriu[idx]);>>> minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->mida == 1);>>> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->matriu[0];>>> minHeap->matriu[0] = minHeap->array[minHeap->mida - 1];>>> >--minHeap->mida;>>> 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->mida;>>> int> i = minHeap->mida - 1;>>> >while> (i> >&& minHeapNode->freqüència>>> array[(i - 1) / 2]->freqüència) {>> > >minHeap->matriu[i] = minHeap->matriu[(i - 1) / 2];>>> i = (i - 1) / 2;> >}> > >minHeap->matriu[i] = minHeapNode;>>> > // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->mida - 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->esquerra) && !(arrel->dreta);  } // Crea un munt mínim de capacitat // igual a la mida i insereix tots els caràcters de // dades[] al munt mínim. Inicialment, la mida de // minúscula és igual a la capacitat struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap (mida);     for (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = mida; buildMinHeap (minHeap); retorn minHeap; } // La funció principal que construeix l'estructura de l'arbre de Huffman MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *esquerra, *dreta, *superior // Pas 1: Creeu un munt mínim de capacitat // igual a la mida; . Inicialment, hi ha // modes iguals a struct MinHeap* minHeap = createAndBuildMinHeap (data, freq, size // Itera mentre la mida de l'heap no es converteix en 1 mentre (!isSizeOne(minHeap)) { //. Pas 2: extreu els dos elements mínims // freq de min Heap left = extractMin(minHeap right = extractMin(minHeap // Pas 3: Creeu un nou node // intern amb freqüència igual a la // suma); freqüències de dos nodes // Fes que els dos nodes extrets siguin // fills esquerre i dret d'aquest nou node // Afegeix aquest node a la pila mínima // '$' és un valor especial per als nodes interns, no //. usat top = newNode('$', left->freq + right->freq);     superior->esquerra = esquerra;   superior->dreta = dreta;     insertMinHeap(minHeap, a dalt);   } // Pas 4: el node restant és el // node arrel i l'arbre està complet.   retorn extractMin(minHeap);  } // Imprimeix codis Huffman des de l'arrel de l'arbre Huffman.  // Utilitza arr[] per emmagatzemar codis void printCodes(struct MinHeapNode* root, int arr[], int top) { // Assigna 0 a la vora esquerra i es repeteix si (root->left) { arr[top] = 0 ;   printCodes(arrel->esquerra, arr, superior + 1);   } // Assigna 1 a la vora dreta i es repeteix si (arrel->dreta) { arr[superior] = 1;   printCodes(arrel->dreta, arr, superior + 1);   } // Si aquest és un node fulla, aleshores // conté un dels // caràcters d'entrada, imprimiu el caràcter // i el seu codi des de arr[] if (isFulla(arrel)) { cout ': ';   printArr(arr, superior);   } } // La funció principal que construeix // un arbre de Huffman i imprimeix codis travessant // l'arbre de Huffman construït void HuffmanCodes(char data[], int freq[], int size) { // Construeix l'estructura de l'arbre de Huffman MinHeapNode* root = buildHuffmanTree (dades, freqüència, mida);     // Imprimeix codis Huffman utilitzant // l'arbre Huffman construït a sobre int arr[MAX_TREE_HT], top = 0;     printCodes (arrel, arr, superior);  } // Codi del controlador int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '};   int freq[] = { 5, 9, 12, 13, 16, 45 };     int size = sizeof (arr) / sizeof (arr[0]);     HuffmanCodes (arr, freqüència, mida);     retorn 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>->dades = dades;>>> this>->freqüència = freqüència;>>> }> };> > // For comparison of> // two heap nodes (needed in min heap)> struct> compare {> > >bool> operator()(MinHeapNode* l, MinHeapNode* r)> > >{> >return> (l->freqüència> r->freq);>>> }> };> > // Prints huffman codes from> // the root of Huffman Tree.> void> printCodes(>struct> MinHeapNode* root, string str)> {> > >if> (!root)> >return>;> > >if> (root->dades !=>>>)> >cout ': ' << str << '
';     printCodes(root->esquerra, str + '0');   printCodes(arrel->dreta, str + '1');  } // La funció principal que construeix un arbre de Huffman i // imprimeix codis travessant l'arbre de Huffman construït void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top;     // Crea un munt mínim i insereix tots els caràcters de les dades[] priority_queue compare> minHeap;     per (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Itera mentre la mida de l'heap no es converteix en 1 mentre (minHeap.size() != 1 ) { // Extraieu els dos elements de freq min. left = minHeap.pop ( right = minHeap.pop (); amb // freqüència igual a la suma de les // freqüències de dos nodes Fes que els // dos nodes extrets siguin fills // d'aquest nou node // a l'heap mín '$' un valor especial // per als nodes interns, no s'utilitza top = new MinHeapNode('$', left->freq + right->left = left top->right = right; (top); } // Imprimeix els codis de Huffman utilitzant // l'arbre de Huffman construït a sobre printCodes(minHeap.top(), '' } // Codi del controlador int main() { char arr[] = { '); a', 'b', 'c', 'd', 'e', 'f' } int freq[] = { 5, 9, 12, 13, 16 , 45 }; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, freq, size);     retorn 0;  } // Aquest codi és aportat per Aditya Goel>>>
 
 
 
 
    
 
> 
com executar un script
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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) { // extracte del primer min.   HuffmanNode x = q.peek();   q.poll();     // extracte de segon min.   HuffmanNode y = q.peek();   q.poll();     // nou node f que és igual HuffmanNode f = nou HuffmanNode();     // a la suma de la freqüència dels dos nodes // assignant valors al node f.   f.data = x.data + y.data;   f.c = '-';     // primer node extret com a fill esquerre.   f.esquerra = x;     // el segon node extret com a fill adequat.   f.dreta = y;     // marcant el node f com a node arrel.   arrel = f;     // afegeix aquest node a la cua de prioritats.   q.add(f);   } // imprimeix els codis travessant l'arbre printCode(arrel, '');   } } // La classe de nodes és l'estructura bàsica // de cada node present a l'arbre de Huffman.  classe HuffmanNode { int dades;   char c;     HuffmanNode a l'esquerra;   HuffmanNode dret;  } // La classe comparadora ajuda a comparar el node // sobre la base d'un dels seus atributs.  // Aquí serem comparats // sobre la base dels valors de dades dels nodes.  class MyComparator implementa Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data;   } } // Aquest codi és aportat per Kunwar Desh Deepak Singh>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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}') # caràcters per a caràcters de l'arbre Huffman = ['a', 'b', 'c', 'd', 'e', 'f'] # freqüència de caràcters freq = [5, 9, 12, 13, 16, 45] # llista que conté nodes de nodes no utilitzats = [] # conversió de caràcters i freqüències # en nodes de l'arbre huffman per a x dins l'interval (len(cars)): heapq .heappush(nodes, node(freq[x], chars[x])) mentre len(nodes)> 1: # ordena tots els nodes en ordre ascendent # segons la seva freqüència left = heapq.heappop(nodes) right = heapq .heappop(nodes) # assigneu un valor direccional a aquests nodes left.huff = 0 right.huff = 1 # combineu els 2 nodes més petits per crear # nou node com a pare nouNode = node(left.freq+right.freq, left. symbol+right.symbol, esquerra, dreta) heapq.heappush (nodes, nouNode) # L'arbre Huffman està preparat!  printNodes(nodes[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) { // extracte del primer min.   sigui x = q[0];   q.shift();     // extracte de segon min.   sigui y = q[0];   q.shift();     // nou node f igual que f = nou HuffmanNode();     // a la suma de la freqüència dels dos nodes // assignant valors al node f.   f.data = x.data + y.data;   f.c = '-';     // primer node extret com a fill esquerre.   f.esquerra = x;     // el segon node extret com a fill adequat.   f.dreta = y;     // marcant el node f com a node arrel.   arrel = f;     // afegeix aquest node a la cua de prioritats.   q.push(f);   q.sort(funció(a,b){retorna a.data-b.data;});   } // imprimeix els codis travessant l'arbre printCode(arrel, '');    // Aquest codi és aportat per 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>
 
 
 
 
    
 
>
 
    
 
>
 
  Sortida  
 
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
 
  Complexitat temporal: O(nlogn) on n és el nombre de caràcters únics. Si hi ha n nodes, extractMin() s'anomena 2*(n – 1) vegades. extractMin() triga temps O(logn) quan crida a minHeapify(). Per tant, la complexitat global és O(nlogn). 
Si la matriu d'entrada està ordenada, existeix un algorisme de temps lineal. Aviat parlarem d'això en el nostre proper post.
 
  Complexitat espacial: - O(N)  
 
Aplicacions de la codificació Huffman:
 
 
S'utilitzen per transmetre fax i text.
 
S'utilitzen en formats de compressió convencionals com PKZIP, GZIP, etc.
 
Els còdecs multimèdia com JPEG, PNG i MP3 utilitzen la codificació Huffman (per ser més precisos els codis de prefix).
 
 
És útil en els casos en què hi ha una sèrie de caràcters que apareixen amb freqüència.
 
    Referència:     
  http://en.wikipedia.org/wiki/Huffman_coding   
Aquest article està compilat per Aashish Barnwal i revisat per l'equip de techcodeview.com.