# Huffman Code in C++

This is my version of the Huffman Codes.

/*
Author: Stevan Milic
Date: 05.05.2018.
Course: Data Structures II
Professor: Dr. Claude Chaudet
Description: Huffman Codes
*/
#include <iostream>
#include <cstdlib>
using namespace std;
#define MAX_TREE_HEIGHT 1000

// A Huffman tree node
struct MinHeapNode
{
char codeword; // I chose char because we are inputing alphabetic       letters

// The reason why I chose unsigned data type is because an unsigned  integer can never be negative.
// In this case the frequency and the capacity of a character cannot be negative.
unsigned freq; // Frequency of the character - how many times does it occur

struct MinHeapNode *left, *right; // Left and Right children
};

struct MinHeap // Collection of nodes
{
unsigned size; // Size of the heap
unsigned capacity; // Capacity of the heap
struct MinHeapNode** array; // Heap node pointers array
};

// Function to dynamically alocate a new heap node with provided character   (codeword) and its frequency
struct MinHeapNode* newHeapNode(char codeword, unsigned freq)
{
struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct   MinHeapNode));

temp->left = temp->right = NULL;
temp->codeword = codeword;
temp->freq = freq;

return temp;
}

// Creating a new dynamically allocated min heap with given capacity
struct MinHeap* createMinHeap(unsigned capacity)
{
struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
minHeap->size = 0; // Setting the size to 0
minHeap->capacity = capacity; // Inserting the given capacity
// Inserting into the heap node pointers array
minHeap->array= (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));
return minHeap;
}

// Swap function to swap two min heap nodes
void swap(struct MinHeapNode** a, struct MinHeapNode** b)
{
struct MinHeapNode* temp2 = *a;
*a = *b;
*b = temp2;
}
// minHeapify function
void minHeapify(struct MinHeap* minHeap, int index)
{
int smallest = index;
int leftSon = 2 * index + 1;
int rightSon = 2 * index + 2;

if (leftSon < minHeap->size && minHeap->array[leftSon]->freq <      minHeap->array[smallest]->freq)
smallest = leftSon;

if (rightSon < minHeap->size && minHeap->array[rightSon]-> freq < minHeap->array[smallest]->freq)
smallest = rightSon;

if (smallest != index)
{
swap(&minHeap->array[smallest], &minHeap->array[index]);
minHeapify(minHeap, smallest);
}
}

// Checking if the size of the heap is 1
int heapSizeOne(struct MinHeap* minHeap)
{
return (minHeap->size == 1);
}

// Extracting minimum value node from the heap
struct MinHeapNode* extractMin(struct MinHeap* minHeap)
{
struct MinHeapNode* temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}

// Inserting a new node into min heap
void insert(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode)
{
++minHeap->size;
int i = minHeap->size - 1;
while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq)
{
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = minHeapNode;
}

// Build function to build min heap
void build(struct MinHeap* minHeap)
{
int n = minHeap->size - 1;
for (int i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
}

// Display function to print an array
void display(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
cout << arr[i];
cout << "\n";
}

// Function to check if the node is a leaf
int isLeaf(struct MinHeapNode* root)
{
return !(root->left) && !(root->right);
}

// Creating a min heap with given capacity equivalent to size and inserts all    the codewords and their frequency.
struct MinHeap* create(char codeword[], int freq[], int size)
{
struct MinHeap* minHeap = createMinHeap(size);
for (int i = 0; i < size; ++i)
minHeap->array[i] = newHeapNode(codeword[i], freq[i]);
minHeap->size = size;
build(minHeap);
return minHeap;
}

// Function that builds the Huffman tree
struct MinHeapNode* buildHT(char codeword[], int freq[], int size)
{
struct MinHeapNode *left, *right, *top;

// Creating a min heap with given capacity equivalent to size and inserts all the codewords and their frequency.
struct MinHeap* minHeap = create(codeword, freq, size);

// while loop runs as long as the size of heap doesn't reach 1
while (!heapSizeOne(minHeap))
{
// Getting the two minimums from min heap
left = extractMin(minHeap);
right = extractMin(minHeap);

// The frequency of top is computed as the sum of the frequencies of left and right nodes.
top = newHeapNode('_', left->freq + right->freq);
top->left = left;
top->right = right;
insert(minHeap, top);
}
// The remaining value is the root node which completes the tree
return extractMin(minHeap);
}

// Prints huffman codes from the root of
// Displaying Huffman codes
void displayHC(struct MinHeapNode* root, int arr[], int top)
{

// Left side is given the value 0
if (root->left)
{
arr[top] = 0;
displayHC(root->left, arr, top + 1);
}
// Right side is given the value 1
if (root->right)
{
arr[top] = 1;
displayHC(root->right, arr, top + 1);
}
// If this is a leaf node, print the character and its code.
if (isLeaf(root))
{
cout << root->codeword << ": ";
display(arr, top);
}
}

// Building a Huffman Tree and displaying the codes
void HuffmanCodes(char codeword[], int freq[], int size)

{
// Building a HT
struct MinHeapNode* root = buildHT(codeword, freq, size);

// Displaying the HT we built
int arr[MAX_TREE_HEIGHT], top = 0;

displayHC(root, arr, top);
}

// I used the example from the PP presentation in the Files section - The Hoffman Coding
int main()
{
cout << "A|4\t B|0\t C|2\t D|1\t C|5\t E|1\t F|0\t G|1\t H|1\t I|0\t J|0\t K|3\t L|2\t M|0\t N|1\t\nO|2\t P|0\t Q|3\t R|5\t S|4\t T|2\t U|0\t V|0\t W|1\t X|0\t Y|0\t Z|0\t _|6\n" << endl;
char arr[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '_' };
int freq[] = { 4, 0, 2, 1, 5, 1, 0, 1, 1, 0, 0, 3, 2, 0, 1, 2, 0, 3, 5, 4, 2, 0, 0, 1, 0, 0, 6};

int size = sizeof(arr) / sizeof(arr[0]);

HuffmanCodes(arr, freq, size);

cout << "\n\n";
system("pause");
return 0;
}

• Your code is pretty much "C with cout and using namespace std;s". It doesn't look like C++ at all. May 5, 2019 at 10:36
• Is this code for an assignment? I'd recommend not putting it online if you haven't yet had it graded.
– TEK
May 5, 2019 at 10:40
• You seem to make the same mistakes over and over again. Could I suggest you consider using some of the answers you are receiving. May 5, 2019 at 20:19
• It looks like you have two different things going on here: A min heap data structure, and an implementation of a huffman code algorithm that happens to use a min heap. Don't conflate the two. Build a generic min heap (that'll come in useful in other places), and build a separate huffman code function that uses it. May 6, 2019 at 2:32
• Which version of C++ are you using? (command line parameters or compiler version would be useful ) May 6, 2019 at 8:17

Looks pretty readable and I agree with most of your formatting however there are some things that stand out.

• using namespace std;
Kick this habit before it kicks you.

• #define MAX_TREE_HEIGHT 1000
I'd prefer to put this into an anonymous namespace as implementation detail

• unsigned freq;
Not everyone knows this defaults to int. Might be a good idea to add int for readability

• At a glance this seems to leak memory
Confirm with valgrind. You're using malloc but no free. Better use new/delete, even better use smart pointers and friends.

• Braces (highly subjective)
Many people disagree on this one but I prefer to always include braces where possible

• Prefer using \n over std::endl

• system("pause"); should be avoided

Overall this seems very C-ish, not so much like (modern) C++. Are you perhaps prohibited from using certain language features?

• 1. It doesn't matter if the #define is in a namespace, as it doesn't respect them anyway. 2. Nobody who needs unsigned int spelled out can legitimately claim even passing familiarity with C++, so they should not be the target audience. 3. return 0; can always be omitted from main(), but nowhere else. May 5, 2019 at 9:02
• "Not everyone knows this defaults to int." - People not knowing that should not touch others code anyway. May 5, 2019 at 10:15
• you complain it looks to "C-ish" but also that he uses the correct std::endl over the very C-ish \n. Make up your mind :) May 6, 2019 at 11:23
• @jwenting How is the character \n related to C at all? How is std::endl correct when it has side-effects which are not desirable here? May 6, 2019 at 12:57
• @yuri Thank you very much for your answer, I tried to correct the mistakes you wrote but somehow I still get the wrong output. It seems like I have a logic error in my code and I can't figure it out. May 8, 2019 at 4:27
• NEVER use using namespace std. It can cause hard tracked bugs. Read here why: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice

• The code has WAY to much comments. "Well commented" does not mean that it should have tons of comments. I have seen well commented code without comments. A problem with comments is that you need to maintain them. Will you remember to change comments when you change the code? Probably not. An example of a completely useless comment is minHeap->size = 0; // Setting the size to 0. You have a variable called size and you're assigning it to the value 0. There's no need for a comment there.

• If you're coding C++, then code C++. No reason to use malloc in C++, because this language has far easier and secure methods for allocating memory.

• On the other hand, minHeap->size = 0; // make heap empty is a comment that might be useful May 5, 2019 at 17:02
• @HagenvonEitzen I disagree. Sure, it gives a little information, but it's not worth it. It's just noise. When I am about to write a comment, I always think if I instead can rewrite the code so that the comment is not necessary. May 5, 2019 at 17:07

Prefer Constants Over Macros
The line

#define MAX_TREE_HEIGHT 1000


might be better written as

const size_t MAX_TREE_HEIGHT = 1000;


In C++ constants are preferred over macros because constants are type safe and provide more error checking at compile time.

Prefer new Type(); Over malloc()
The C++ programming language allowed malloc(), calloc() and free() for backwards comparability with the C programming language, however, it also introduced new Type() and delete(). Generally new and delete are preferred over the older C language functions. Using new has these benefits:

• new is an operator, malloc is a function
• new returns the proper type so the cast is not necessary
• new executes constructors to properly initialize the new object, the use of malloc requires additional code to initialize the new object.
• new automatically performs the error checking for failed memory allocation and throws an exception if the allocation failed. For malloc additional code needs to be added to make sure malloc did not return NULL (or nullptr in the case of C++).
• new knows the amount of memory to allocate for the object, malloc requires the programmer to specify the size of the object.

References about new versus malloc can be found here, here and this stackoverflow question.

When allocating arrays in C calloc() is preferred over malloc() for two reasons, first it is clear that an array is being allocated because there are two arguments, one is the size of the array and the other is the size of the object. The second reason is that calloc() clears the memory of the objects (initializes the entire array contents to zero), malloc() requires the programmer to clear the contents of the array.

Namespaces
Namespaces were added to the definition of the C++ language to prevent collisions of function names and variables. Operators such as cin and cout can be overloaded to display the contents of objects. In this case the overloaded NAMESPACE::cout may include references to std::cout. Generally using namespace std; is considered a bad programming practice because it can cause function name or variable name collisions. For maintainability reasons never put using namespace std; into a header file.

Use Container Classes When Possible
The array allocated by this line

    struct MinHeap* minHeap = createMinHeap(size);


might be better as the C++ container class std::vector or even std::vector (does the code really need the pointers).

std::vector is a variable sized array of any type, it grows as needed.