Test and Add Huffman Code

[LuchoBazz]

const char SPECIAL_CH = '$';
const string FIRST_ALPHA = "0";
const string SECOND_ALPHA = "1";
struct HffTreeNode {
    // One of the input characters
    char ch;
    // Frequency of the character
    uint32_t freq;
    // Left and right child
    HffTreeNode *left, *right;
    HffTreeNode(char ch, uint32_t freq) {
        left = right = NULL;
        this->ch = ch;
        this->freq = freq;
    }
};

struct Code {
    char ch;
    string bin;
};

// For comparison of
// two heap nodes (needed in min heap)
struct Compare {
    bool operator()(HffTreeNode* l, HffTreeNode* r) {
        return l->freq > r->freq;
    }
};
 
// Prints huffman codes from
// the root of Huffman Tree.
void buildCodes(vector<Code> &codes, struct HffTreeNode* root, string str) {
    if (!root) return;
    if (root->ch != SPECIAL_CH) codes.push_back(Code{root->ch, str});
    buildCodes(codes, root->left, str + FIRST_ALPHA);
    buildCodes(codes, root->right, str + SECOND_ALPHA);
}
 
// The main function that builds a Huffman Tree and
// print codes by traversing the built Huffman Tree
HffTreeNode* HuffmanCodes(vector<char> alpha, vector<int> freq) {
    int size = (int) alpha.size();
    struct HffTreeNode *left, *right, *top;
    // Create a min heap & inserts all characters of alpha[]
    priority_queue<HffTreeNode*, vector<HffTreeNode*>, Compare> minHeap;
    
    for (int i = 0; i < size; ++i) {
        minHeap.push(new HffTreeNode(alpha[i], freq[i]));
    }
    #define pop_heap(heap) heap.top(); heap.pop();
    
    // Iterate while size of heap doesn't become 1
    while (minHeap.size() != 1) {
        // Extract the two minimum
        // freq items from min heap
        left = pop_heap(minHeap);
        right = pop_heap(minHeap);
        // 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 HffTreeNode(SPECIAL_CH, left->freq + right->freq);
        top->left = left;
        top->right = right;
        minHeap.push(top);
    }
    return minHeap.top();
}

// Usage:
// vector<char> alpha = { 'a', 'b', 'c', 'd', 'e', 'f' };
// vector<int> freq = { 5, 9, 12, 13, 16, 45 };
// HffTreeNode* root = HuffmanCodes(alpha, freq);
// vector<Code> codes;
// buildCodes(codes, root, "");
// for(auto &code: codes) cout << code.ch << ": " << code.bin << endl;