Binary Huffman Code in C++

Huffman code is an optimal code for the given source (probability distribution), which assigns small length codes to high frequent symbols. For more information click here.

GenHuffmanCode.cpp

#include "MinPriorityQueue.cpp"

using namespace std;

class Node {
public:
    string name;
    int f;
    Node *left, *right;
    string code;

    Node() {
        name = "";
        code = "";
        f = INT_MAX;
        left = right = 0;
    }

    Node(int ff, string n = "") {
        name = n;
        f = ff;
        left = right = 0;
        code = "";
    }

    ~Node() {
        delete left;
        delete right;
    }

    bool operator<(Node &param) {
        return f < param.f;
    }

    bool operator>(Node &param) {
        return f > param.f;
    }

    bool operator==(Node &param) {
        return f == param.f;
    }

    static void display(Node*, bool);
    static void encode(Node*);

    friend ostream& operator <<(ostream&, Node&);
};

void Node::display(Node* node, bool leavesOnly = 1) {
    if (node == 0) {
        return;
    }
    display(node->left, leavesOnly);
    if (leavesOnly) {
        if (node->left == 0 && node->right == 0) {
            cout << *node << ", ";
        }
    } else {
        cout << *node << ", ";
    }
    display(node->right, leavesOnly);
}

void Node::encode(Node* node) {
    if (node == 0) {
        return;
    }
    if (node->left != 0) {
        node->left->code = node->code + "0";
    }
    if (node->right != 0) {
        node->right->code = node->code + "1";
    }
    encode(node->left);
    encode(node->right);
}

ostream& operator <<(ostream &out, Node &node) {
    out << node.name << "(" << node.f << ")" << ":" << node.code;
    return out;
}

void HuffmanCode(int *freqs, string* names, int length) {
    Q<Node> *q = new Q<Node > (length);
    for (int i = 0; i < length; i++) {
        q->insert(new Node(freqs[i], names[i]));
    }

    for (int i = 0; i < length - 1; i++) {
        Node *x = q->extractMin();
        Node *y = q->extractMin();
        Node *z = new Node(x->f + y->f, x->name + y->name);
        z->left = x;
        z->right = y;
        q->insert(z);
    }
    Node *root = q->extractMin();
    cout << "Full tree (inorder):\n";
    Node::display(root, 0);
    cout << "\nHuffman Code:\n";
    Node::encode(root);
    Node::display(root);
}

int main(int argc, char** argv) {
    int freqs[] = {45, 13, 12, 16, 9, 5};
    string names[] = {"a", "b", "c", "d", "e", "f"};
    HuffmanCode(freqs, names, 6);
    return 0;
}

Output

Full tree (inorder):
a(45):, acbfed(100):, c(12):, cb(25):, b(13):, cbfed(55):, f(5):, fe(14):, e(9):, fed(30):, d(16):, 
Huffman Code:
a(45):0, c(12):100, b(13):101, f(5):1100, e(9):1101, d(16):111, 

Minimum Priority Queue Implemented Using Min-Heap in C++

MinPriorityQueue.h

#ifndef MINPRIORITYQUEUE_H
#define MINPRIORITYQUEUE_H

template<class T> class Q {
    int array_size, heap_size;
    T** A; // pointer for the array    

public:
    Q(int s);
    ~Q();
    bool isEmpty();
    bool isFull();
    T** getArray();
    int getArraySize();
    T* minimum();
    T* extractMin();
    bool insert(T*);

private:
    int left(int i);
    int right(int i);
    int parent(int i);
    void decreaseKey(int, T*);
    void minHeapify(int);
};

#endif /* MINPRIORITYQUEUE_H */

MinPriorityQueue.cpp

#include <cstdlib>
#include <iostream>
#include "MinPriorityQueue.h"

using namespace std;

template<class T> Q<T>::Q(int s) {
    array_size = s;
    heap_size = -1;
    A = new T*[s];
}

template<class T> Q<T>::~Q() {
    delete A;
}

template<class T> bool Q<T>::isEmpty() {
    return heap_size < 0;
}

template<class T> bool Q<T>::isFull() {
    return heap_size >= array_size - 1;
}

template<class T> T** Q<T>::getArray() {
    return A;
}

template<class T> int Q<T>::getArraySize() {
    return array_size;
}

template<class T> T* Q<T>::minimum() {
    return A[0];
}

template<class T> int Q<T>::left(int i) {
    return 2 * (i + 1) - 1;
}

template<class T> int Q<T>::right(int i) {
    return 2 * (i + 1);
}

template<class T> int Q<T>::parent(int i) {
    return max((i + 1) / 2 - 1, 0);
}

template<class T> T* Q<T>::extractMin() {
    if (isEmpty()) {
        cout << "Underflow...\n";
        T* t;
        return t;
    } else {
        T* min = A[0];
        A[0] = A[heap_size];
        heap_size--;
        minHeapify(0);
        return min;
    }
}

template<class T> void Q<T>::minHeapify(int i) {
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l <= heap_size && ((*(A[l])) < (*(A[i])))) {
        smallest = l;
    }
    if (r <= heap_size && ((*(A[r])) < (*(A[smallest])))) {
        smallest = r;
    }
    if (smallest != i) {
        T* t = A[i];
        A[i] = A[smallest];
        A[smallest] = t;
        minHeapify(smallest);
    }
}

template<class T> bool Q<T>::insert(T* key) {
    if (isFull()) {
        cout << "Overflow...\n";
        return false;
    } else {
        heap_size++;
        decreaseKey(heap_size, key);
        return true;
    }
}

template<class T> void Q<T>::decreaseKey(int i, T* key) {
    A[i] = key;
    while ((i > 0) && ((*(A[parent(i)])) > (*(A[i])))) {
        T* t = A[i];
        A[i] = A[parent(i)];
        A[parent(i)] = t;
        i = parent(i);
    }
}

TestMinPriorityQueue.cpp

#include "MinPriorityQueue.cpp"

using namespace std;

void testMinPQ() {
    Q<int> *q = new Q<int>(10);
    int x[] = {10, 5, 8, 15, 4, 20, 28, 33, 11, 3};
    for (int i = 0; i < 10; i++) {
        q->insert(&x[i]);
    }
    for (int i = 0; i < 10; i++) {
        cout << (*q->extractMin()) << ", ";
    }
}

int main(int argc, char** argv) {
    testMinPQ();
    return 0;
}

Output

3, 4, 5, 8, 10, 11, 15, 20, 28, 33,

Lowest Common Multiplier and Greatest Common Divisor in Python

Lowest Common Multiplier (LCM) and Greatest Common Divisor (GCD) can be found for any list of numbers by this code. 
LCM x GCD = FACT(x1,x2,...xn)
Here, FACT(x1,x2,...xn) is the multiplication of the input arguments x1 to xn. I used the above equation to find the GCD by calculating LCM first. However, you can calculate GCD directly using Euclid's algorithm.

Code

def lcm(x,y):
    tmp=x
    while (tmp%y)!=0:
        tmp+=x
    return tmp

def lcmm(*args):
    return reduce(lcm,args)

def fact(args):
    if len(args) == 0:
        return 1
    else:
        return args[0] * fact(args[1:])

def gcd(args):
    return fact(args)/lcmm(*args)

args=range(1,11)
print args
print 'LCM:', lcmm(*args)
print 'GCD:', gcd(args)

Euclid's Algorithm

def gcd(a, b):
    while b:      
        a, b = b, a % b
    return a

Question

Find the sequence of numbers whose remainder is one less than its divisor?
Eg. Consider N, N mod x = x - 1 for x in list 1 - 20. Find the sequence of N?

Ans. Find the LCM of list 1 - 20, then N = k * LCM - 1, where k is an integer.