Жадные алгоритмыКоды ХаффманаСжатие данныхАлгоритмы
1 мин чтение
Жадные алгоритмы, Выбор процессов и Оптимальные коды Хаффмана
Принцип жадного выбора и оптимальная подструктура. Задача о выборе непересекающихся отрезков (Activity Selection). Построение оптимального префиксного дерева Хаффмана через очередь с приоритетами за O(K log K).
Исходная заготовка: полнота объяснения и примеров ожидает редакторской проверки.
Принцип жадного выбора
Жадный алгоритм на каждом шаге принимает локально оптимальное решение в надежде получить глобально оптимальный результат.
Жадный подход корректен, если задача обладает двумя свойствами:
Алгоритм сжатия Хаффмана (Huffman Coding)
Коды Хаффмана строят оптимальный префиксный код переменной длины (символы с высокой частотой получают короткие битовые последовательности).
cpp
struct Node {
char ch;
int freq;
Node *left, *right;
};
struct Compare {
bool operator()(Node* a, Node* b) { return a->freq > b->freq; }
};
Node* buildHuffmanTree(const map<char, int>& freqs) {
priority_queue<Node*, vector<Node*>, Compare> pq;
for (auto [ch, f] : freqs) pq.push(new Node{ch, f, nullptr, nullptr});
while (pq.size() > 1) {
Node* left = pq.top(); pq.pop();
Node* right = pq.top(); pq.pop();
Node* parent = new Node{'\0', left->freq + right->freq, left, right};
pq.push(parent);
}
return pq.top();
}Что дальше?
Закрепите материал задачей: Повторить число.
Изучено — к практике →Отметка сохранится в этом браузере. Её можно отменить или снять кнопкой «Изучено».