6
\$\begingroup\$

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;
}
\$\endgroup\$
  • 16
    \$\begingroup\$ Your code is pretty much "C with cout and using namespace std;s". It doesn't look like C++ at all. \$\endgroup\$ – L. F. May 5 at 10:36
  • 6
    \$\begingroup\$ Is this code for an assignment? I'd recommend not putting it online if you haven't yet had it graded. \$\endgroup\$ – TEK May 5 at 10:40
  • 10
    \$\begingroup\$ You seem to make the same mistakes over and over again. Could I suggest you consider using some of the answers you are receiving. \$\endgroup\$ – bruglesco May 5 at 20:19
  • \$\begingroup\$ 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. \$\endgroup\$ – Alexander May 6 at 2:32
  • \$\begingroup\$ Which version of C++ are you using? (command line parameters or compiler version would be useful ) \$\endgroup\$ – Robert Andrzejuk May 6 at 8:17
14
\$\begingroup\$

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

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

\$\endgroup\$
  • 8
    \$\begingroup\$ 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. \$\endgroup\$ – Deduplicator May 5 at 9:02
  • 9
    \$\begingroup\$ "Not everyone knows this defaults to int." - People not knowing that should not touch others code anyway. \$\endgroup\$ – klutt May 5 at 10:15
  • \$\begingroup\$ 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 :) \$\endgroup\$ – jwenting May 6 at 11:23
  • 3
    \$\begingroup\$ @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? \$\endgroup\$ – Vincent Savard May 6 at 12:57
  • \$\begingroup\$ @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. \$\endgroup\$ – Stevan Milic May 8 at 4:27
8
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ On the other hand, minHeap->size = 0; // make heap empty is a comment that might be useful \$\endgroup\$ – Hagen von Eitzen May 5 at 17:02
  • \$\begingroup\$ @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. \$\endgroup\$ – klutt May 5 at 17:07
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ new is not normally faster than malloc. Do you have an implementation where it is? \$\endgroup\$ – Anonymous May 5 at 20:47
  • \$\begingroup\$ @Anonymous techdifferences.com/difference-between-new-and-malloc.html see execution. \$\endgroup\$ – pacmaninbw May 5 at 20:55
  • \$\begingroup\$ That source says "The new operator cuts off the execution time as it is an operator, not a function", which is confused — are they thinking it saves function call overhead or something? In reality, new is usually either exactly as fast as malloc (if it compiles to a malloc call) or slightly slower (if it adds an extra wrapper). \$\endgroup\$ – Anonymous May 5 at 21:03
  • \$\begingroup\$ @Anonymous I've removed it from the answer. \$\endgroup\$ – pacmaninbw May 5 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.