Хаффмана Кодирование структур Алгоритм/данных

Question

Таким образом, мы получили задание написать ALG сжатия для .txt текстовых/цифр (предположительно через код хаффмана, так как наш профессор был очень расплывчатым)

У меня есть все линии, как ключи на карте с частотами в качестве их значений. Я немного отрывочен от того, как исходить отсюда, поскольку карты организованы по порядку по ключу не значение Должен ли я использовать другую структуру данных (а не карту) или было бы достаточно просто найти два наименьших значения min каждый раз, когда я хотел добавить к дереву? Код ниже, любая помощь была бы потрясающей!

#include <iostream> 
#include <fstream> 
#include <sstream> 
#include <string> 
#include <algorithm> 
#include <vector> 
#include <map> 
using namespace std; 

int main() 
{ 
    vector <string> words; 
    map <string, int> store; 
    ifstream infile("file.txt"); 
    string text; 
    while (getline(infile, text)) 
    { 
     istringstream iss(text); 
     string input; 
     if (!(iss >> input)) 
      break; 
     words.push_back(input); 
    } 
    int freq = 0; 


    while (!words.empty()) 
    { 

     string check = words[0]; 
     if(check == "") //make sure not reading a blank 
     { 
      words.erase(remove(words.begin(), words.end(), "")); //remove all blanks 
      continue; //top of loop 
     } 
     check = words[0]; 
     freq = count(words.begin(), words.end(), check);//calculate frequency 
     store.insert(pair<string, int>(check, freq)); //store words and frequency in map 
     words.erase(remove(words.begin(), words.end(), check)); //erase that  value entirely from the vector 
    } 

    map<string, int>::iterator i; 

    for(i = store.begin(); i != store.end(); ++i) 
    { 
     cout << "store[" << i ->first << "] = " << i->second << '\n'; 
    } 
    return 0; 
} 

Answer 1

Чтобы найти значение min вы можете использовать Priority Queue.

ОчередьПриоритет представляет собой структуру данных, которая может дать вам минимальное или максимальное значение из набора элементов. Обнаружение или вставка в него стоит O(log(n)). Поэтому в этом случае это может быть идеальным выбором.

C++ имеет собственную встроенную очередь приоритетов.

Вот простой пример priority_queue в C++.

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
    priority_queue <int> Q; 

    Q.push(10); 
    Q.push(7); 
    Q.push(1); 
    Q.push(-3); 
    Q.push(4); 

    while(!Q.empty()){ // run this loop until the priority_queue gets empty 

     int top = Q.top(); 
     Q.pop(); 
     cout << top << ' '; 

    } 
    cout << endl; 
    return 0; 
} 

Выход

10, 7, 4, 1, -3 

И как вы можете заметить, что это в порядке возрастания. Это потому, что:

По умолчанию Priority Queue дает наивысшее значение.

Таким образом, вы можете либо перегрузить очередь приоритетов, либо очень умный трюк может хранить значения, инвертируя их знаки и после того, как вы выскочите их из очереди, вы можете снова инвертировать знак.