huffman

#include <iostream>
#include <fstream>
using namespace std;

/*
Node definition for our min heap / huffman tree.
*/
struct Node {
    int frequency;
    char data;
    Node* left;
    Node* right;
};

typedef struct Node Node;

/*
Heap class which is what our huffman tree will create and use.
*/
class Heap {
public:
    // Variables.
    int size;
    int capacity;
    struct Node** array;
    // Functions.
    Heap(char _data[], int _freq[], int _size); // Constructor. Creates a new heap of given capacity.
    Node* newNode(char _data, int _freq); // Create a new node for the heap.
    void swapNodes(Node** first, Node** second); // Swap two nodes in place. (Basically changing pointers of them.)
    void heapify(int index); // Time to heapify.
    bool isSizeOne(); // Check size of heap.
    Node* minNode(); // Get minimum node.
    void insertNode(Node* newHeapNode); // Insert a new node.
    void buildHeap(); // Build the heap using heapify.
};

/*
The class which makes the huffman tree and it's codes for output.
*/
class Huffman {
public:
    // Makes tree and then prints out the code values as needed.
    Huffman(char data[], int freq[], int size);
    // Builds huffman tree.
    Node* buildHuffmanTree(char data[], int freq[], int size);
    // Print out codes (i.e. 10101010101001111, etc.)
    void printCodes(Node* root, int array[], int top);
    bool isLeaf(Node* root); // Check if a node is a leaf node.
    void printArray(int array[], int n);
};

// Constructor will create our heap.
Heap::Heap(char _data[], int _freq[], int _size)
{
    capacity = _size;
    array = (struct Node**)malloc(capacity * sizeof(struct Node*)); // Creates the array for all the nodes needed.
    for (int i = 0; i < _size; i++) {
        array[i] = newNode(_data[i], _freq[i]);
    }
    size = _size;
    buildHeap();
}

// Create a new node in memory with given arguments and returns it.
Node* Heap::newNode(char _data, int _freq)
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->left = NULL;
    temp->right = NULL;
    temp->data = _data;
    temp->frequency = _freq;
    return temp;
}

// Swap two nodes in place. (Basically changing pointers of them.)
void Heap::swapNodes(Node** first, Node** second)
{
    Node* temp = *first;
    *first = *second;
    *second = temp;
}

void Heap::heapify(int index)
{
    int smallest = index;
    int right = (2 * index) + 2;
    int left = (2 * index) + 1;
    if ((left < size) && (array[left]->frequency < array[smallest]->frequency)) {
        smallest = left;
    }
    if ((right < size) && (array[right]->frequency < array[smallest]->frequency)) {
        smallest = right;
    }
    if (smallest != index) {
        swapNodes(&array[smallest], &array[index]);
        heapify(smallest);
    }
}

bool Heap::isSizeOne()
{
    if (size == 1) {
        return true;
    }
    else {
        return false;
    }
}

Node* Heap::minNode()
{
    Node* temp = array[0];
    array[0] = array[size - 1];
    heapify(0);
    return temp;
}

void Heap::insertNode(Node* newHeapNode)
{
    int i = size;
    size++;
    while ((i) && (newHeapNode->frequency < (array[(i - 1) / 2])->frequency)) {
        array[i] = array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    array[i] = newHeapNode;
}

void Heap::buildHeap()
{
    int n = size - 1;
    for (int i = (n - 1) / 2; i >= 0; i--) {
        heapify(i);
    }
}

bool Huffman::isLeaf(Node* root)
{
    if ((root->left == NULL) && (root->right == NULL)) {
        return true;
    }
    else {
        return false;
    }
}

Huffman::Huffman(char data[], int freq[], int size) {
    Node* rootOfTree = buildHuffmanTree(data, freq, size);
    // Print out the tree. (We assume max size is 100 possible.)
    int array[100];
    int top = 0;
    printCodes(rootOfTree, array, top);
}

Node* Huffman::buildHuffmanTree(char data[], int freq[], int size)
{
    // Our tree node pointers.
    Node *left, *right, *top;
    // Create the min heap.
    Heap minHeap(data, freq, size);
    // Keeps iterating until size is one of the heap.
    while (!minHeap.isSizeOne()) {
        // Pull out lowest 2 freq nodes.
        left = minHeap.minNode();
        right = minHeap.minNode();
        // Create an internal node.
        // # isn't used in the node since internal.
        top = minHeap.newNode('#', (left->frequency + right->frequency));
        top->left = left;
        top->right = right;
        minHeap.insertNode(top);
    }
    return minHeap.minNode();
}

void Huffman::printCodes(Node* root, int array[], int top)
{
    // Recur left, which is assigned a 0.
    if (root->left) {
        array[top] = 0;
        printCodes(root->left, array, (top + 1));
    }
    // Recur right, assigned a 1.
    if (root->right) {
        array[top] = 1;
        printCodes(root->right, array, (top + 1));
    }
    if (isLeaf(root)) {
        printArray(array, top);
    }
}

void Huffman::printArray(int array[], int n)
{
    for (int i = 0; i < n; ++i) {
        cout << array[i];
    }
}

int main() {
    char array[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int freq[] = { 5, 9, 12, 13, 16, 45 };
    int size = sizeof(array) / sizeof(array[0]);
    Huffman tree(array, freq, size);
    return 0;
}