Question

Create this C++ program using classes

1. Create a file text file with a string on it

2. Check the frecuency of every letter, number and symbol (including caps)

3. Use heapsort to sort the frecuencys found

4. Use huffman code on the letters, symbols or numbers that have frecuencys

I created the file, and the frecuency part but i'm having trouble with the huffman and heapsort implementation.

Answer 1

Huffman Code implementation: (I have included the main() for your understanding)

#include <bits/stdc++.h> 
using namespace std;
struct minHeapNode { 
    char data; 
    int freq; 
    minHeapNode *left, *right; 
    minHeapNode(char data, int freq) 
    { 
        left = right = NULL; 
        this->data = data; 
        this->freq = freq; 
    } 
}; 
struct compare { 
  
    bool operator()(minHeapNode* l, minHeapNode* r) 
  
    { 
        return (l->freq > r->freq); 
    } 
}; 
 
void printHuffCodes(struct minHeapNode* root, string str) 
{ 
  
    if (!root) 
        return; 
  
    if (root->data != '$') 
        cout << root->data << ": " << str << "\n"; 
  
    printHuffCodes(root->left, str + "0"); 
    printHuffCodes(root->right, str + "1"); 
} 

void HuffmanCodes(char data[], int freq[], int size) 
{ 
    struct minHeapNode *left, *right, *top; 
    priority_queue<minHeapNode*, vector<minHeapNode*>, compare> minHeap; 
  
    for (int i = 0; i < size; ++i) 
        minHeap.push(new minHeapNode(data[i], freq[i])); 
    while (minHeap.size() != 1) { 
        left = minHeap.top(); 
        minHeap.pop(); 
  
        right = minHeap.top(); 
        minHeap.pop(); 
        top = new minHeapNode('$', left->freq + right->freq); 
  
        top->left = left; 
        top->right = right; 
  
        minHeap.push(top); 
    } 

    printHuffCodes(minHeap.top(), ""); 
} 
int main() 
{ 
  
    char arr[] = { 'a', 'b', 'c', 'd' }; 
    int freq[] = { 24, 27, 21, 15 }; 
  
    int size = sizeof(arr) / sizeof(arr[0]); 
  
    HuffmanCodes(arr, freq, size); 
  
    return 0; 
} 

Heapsort:

#include <bits/stdc++.h> 
using namespace std; 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int left = 2*i + 1; 
    int right = 2*i + 2;  
  
    if (left < n && arr[left] > arr[largest]) // If left child is larger than root
        largest = left; 
  
     
    if (right < n && arr[right] > arr[largest]) // If right child is larger than largest so far
        largest = right; 
  
    if (largest != i)   // If largest is not root 
    { 
        swap(arr[i], arr[largest]); 
        heapify(arr, n, largest); 
    } 
} 
  
void heapSort(int arr[], int n) 
{ 
    for (int i = n / 2 - 1; i >= 0; i--) //Building the heap
        heapify(arr, n, i); 
  
    
    for (int i=n-1; i>0; i--)   // extract an element from heap 
    { 
        swap(arr[0], arr[i]); // Moving the current root to end
        heapify(arr, i, 0);  // call max heapify on the reduced heap
    } 
} 
 
int main() 
{ 
    int arr[] = {38, 21, 25, 1, 8, 49}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout << "Sorted array is: "; 
    for (int i=0; i<n; ++i) 
        cout << arr[i] << " "; 
}