Huffman Code in C++

Question

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

Answer 1

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

• If you don't depend on return values you can omit return 0 from main (subjective)

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

Answer 2

• 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.

Answer 3

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.