d371 - 3. Huffman 編碼中的編碼效能問題

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定頻率的符號集，使用 Huffman 編碼後所需的總位元數。Huffman 編碼是一種變長編碼，頻率高的符號使用較短的編碼，頻率低的符號使用較長的編碼，從而最小化平均編碼長度。

解題思路

本題使用貪心演算法解決。首先，將所有符號的頻率放入一個優先佇列（最小堆）中。然後，重複以下步驟，直到優先佇列中只剩一個元素：

1. 從優先佇列中取出兩個頻率最低的符號。
2. 將這兩個符號的頻率相加，作為新的節點的頻率。
3. 將新的節點放回優先佇列。 每次取出兩個頻率最低的符號時，將它們的頻率加到總位元數中。最後，優先佇列中只剩一個元素時，總位元數即為 Huffman 編碼後的總位元數。

複雜度分析

• 時間複雜度: O(n log n)，其中 n 是符號的數量。這是因為優先佇列的插入和刪除操作需要 O(log n) 的時間，而這些操作在迴圈中執行 n-1 次。
• 空間複雜度: O(n)，因為優先佇列需要存儲所有符號的頻率。

程式碼

#include <iostream>
#include <queue>
using namespace std;
long long int ans,n,s,k;
priority_queue <long long int,vector <long long int> ,greater<long long int > > p;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> k;
		p.push(k);
	}
	for(int i=0;i<n-1;++i){
		long long int x=p.top(),y;
		p.pop();
		y=p.top();
		p.pop();
		ans+=x+y;
		p.push(x+y);
	}
	cout << ans;
}