【算法導論】貪心算法之赫夫曼編碼

        概述

        讨論赫夫曼編碼問題，赫夫曼編碼的思想就是變長編碼。變長編碼就是讓字元表中出現機率高的字元的編碼長度盡可能小，而出現機率高的字元的編碼長度相對較長。然後還要遵循字首碼的要求，就是任意一個編碼都不是其他編碼的字首碼，這樣友善解碼。

        思路及實作

        對于下表中的字元和相應的出現機率，有對應圖中的編碼樹：

        可以比較容易的看出來，每個葉節點就代表一個字元，從根節點到葉節點走過的路徑拼接起來，就代表這個字元的編碼，比如f是1100，e是1101，而f和e是深度最深的節點也是機率最小的兩個節點。這也就是我們要求的赫夫曼編碼形式。這種最優的編碼形式，總是一顆滿的二叉樹。

        算導上有大量的篇幅來論證用貪心算法，每次選擇機率最小的兩個節點來，可以完成赫夫曼編碼。這裡隻說實作方法。

        由于每次都要找出出現機率最小的那個節點，彈出來，并删掉，是以我們可以使用最小優先隊列來做。注意一點是，編碼樹的葉子節點個數等于字元的個數，而内部節點個數則等于字元的個數減去一，是以求内部節點的循環隻需要n-1次即可，n為字元數。

小根堆操作：

#include <iostream>
#include <stack>

using namespace std;

#define MAX_INDEX 11

struct node {
	int freq;
	node* left;
	node* right;
	node() :
			freq(), left(NULL), right(NULL) {
	}
};

//數組從1号元素開始算起
int left_child(int i) {
	return i * 2;
}

int right_child(int i) {
	return i * 2 + 1;
}

int parent(int child) {
	return child / 2;
}

void swap(node* a, node* b) {
	node tmp = *a;
	*a = *b;
	*b = tmp;
}

void Print_Heap(node* a, int len) {
	for (int i = 1; i < len; i++) {
		cout << a[i].freq << ' ';
	}
	cout << endl;
}

/*
 * 将一個左右子樹都是小根堆的堆轉化成小根堆
 */
void Min_Heapify(node heap[], int root, int n) {
	int l = left_child(root);
	int r = right_child(root);

	int min = root;

	if (l <= n && heap[min].freq > heap[l].freq) {
		min = l;
	}

	if (r <= n && heap[min].freq > heap[r].freq) {
		min = r;
	}

	if (min != root) {
		swap(heap + root, heap + min);
		Min_Heapify(heap, min, n);
	}
}

/*
 * 建構一個小根堆
 */
void Build_min_heap(node heap[], int n) {
	int idx = n / 2 + 1;
	for (int i = idx; i >= 1; i--) {
		Min_Heapify(heap, i, n);
	}
}
           

最小優先隊列操作：

/*
 * 最小優先隊列要實作的操作：
 *
 * ①INSERT(S,x)
 *
 * ②MINIMUM(S)
 *
 * ③EXTRACT_MIN(S)
 *
 * ④DECREASE_KEY(S,x,k)
 *
 */

/*
 * 最小優先隊列
 */
struct min_priority_queue {
	node* min_heap;
	int len;

	min_priority_queue(node* mh, int l) :
			min_heap(mh), len(l) {
	}
};

/*
 * 傳回最小元素
 */
node* HEAP_MINIMUM(min_priority_queue* mpq) {
	if (mpq->len < 1) {
		cout << "min_priority_queue underflow" << endl;
	}
	return mpq->min_heap + 1;
}

/*
 * 彈出并移除最小的元素
 */
node* HEAP_EXTRACT_MIN(min_priority_queue* mpq) {

	if (mpq->len < 1) {
		cout << "min_priority_queue underflow" << endl;
	}

	//這裡必須要建立一個節點傳回去，如果直接傳回原節點，則會導緻後面insert的時候，左右孩子的指針指向的内容發生變化

	//建立一個節點
	node* min = new node();

	//複制最小節點的内容到建立節點，最後将建立的節點的指針傳回
	*min = *(mpq->min_heap + 1);

	swap(mpq->min_heap + 1, mpq->min_heap + mpq->len);

	//删除彈出的節點，防止記憶體洩露
	delete (mpq->min_heap + mpq->len);

	//将最後一個節點從堆中去掉
	(mpq->len)--;

	//重新維護小根堆的性質
	Min_Heapify(mpq->min_heap, 1, mpq->len);

	//傳回min
	return min;
}

/*
 * 把優先隊列中原來為x的元素的值，換成k，并維護最小堆的性質
 */
void HEAP_DECREASE_KEY(min_priority_queue* mpq, int i, node* n) {
	if (mpq->min_heap[i].freq < n->freq) {
		cout << "error:要替換的值比原值要大" << endl;
		return;
	}

	mpq->min_heap[i].freq = n->freq;

	while (i >= 1 && mpq->min_heap[i].freq < mpq->min_heap[parent(i)].freq) {
		swap(mpq->min_heap + i, mpq->min_heap + parent(i));
		i = parent(i);
	}
}

/*
 * 插入元素
 */
void HEAP_INSERT(min_priority_queue* mpq, node* n) {
	(mpq->len)++;
	*(mpq->min_heap + mpq->len) = *n;
	HEAP_DECREASE_KEY(mpq, mpq->len, n);
}

/*
 * 列印節點數組
 */
void PRINT_NODE_ARRAY(node* n_arr, int max_index) {
	for (int i = 1; i <= max_index; i++) {
		cout << n_arr[i].freq << ' ';
	}
	cout << endl;
}
           

赫夫曼編碼形成編碼樹：

//哈夫曼編碼樹
struct Huffman_Tree
{
    node *root;
    Huffman_Tree():root(NULL){}
};



/*
 * 赫夫曼編碼，傳回編碼樹的頭結點
 */
void HUFFMAN(min_priority_queue* mpq,Huffman_Tree* T) {
	int n = mpq->len;

	Build_min_heap(mpq->min_heap, n);

	node* tmp = NULL;

	//内部節點有n-1個，是以進行n-1次循環，每一個tmp都是一個内部節點，形成之後，再将tmp入堆，繼續循環
	for (int i = 1; i <= n - 1; i++) {
		tmp = new node();
		tmp->left = HEAP_EXTRACT_MIN(mpq);
		tmp->right = HEAP_EXTRACT_MIN(mpq);
		tmp->freq = tmp->left->freq + tmp->right->freq;
		HEAP_INSERT(mpq, tmp);
	}
//	return HEAP_EXTRACT_MIN(mpq);
	T->root=HEAP_EXTRACT_MIN(mpq);
}

/*
 * 中序周遊編碼樹
 */
void PRINT_CODED_TREE(node* root) {
	if (root != NULL) {
		PRINT_CODED_TREE(root->left);
		cout << root->freq << ' ';
		PRINT_CODED_TREE(root->right);
	}
}

/*
 * 删除編碼樹的節點
 */
void DELETE_CODED_TREE(node* root) {
	if (root != NULL) {
		DELETE_CODED_TREE(root->left);
		node* tmp = root->right;
		delete root;
		root = NULL;
		DELETE_CODED_TREE(tmp);
	}
}

int main() {

	int freq_arr[MAX_INDEX + 1] = { 0, 10, 4, 8, 20, 7, 6, 3, 11, 1, 5, 25 };

	node node_arr[MAX_INDEX + 1];

	for (int i = 0; i < 12; i++) {
		node_arr[i].freq = freq_arr[i];
	}

	//建立一個最小優先隊列對象，應用上面的數組
	min_priority_queue* mpq = new min_priority_queue(node_arr, MAX_INDEX);

	Huffman_Tree* T = new Huffman_Tree();

	HUFFMAN(mpq,T);

	PRINT_CODED_TREE(T->root); //10個内部節點和原來的11個葉子節點，一共21個節點

	DELETE_CODED_TREE(T->root);

	return 0;
}
           

    複雜度分析

        形成小根堆耗時O(n)，而在HUFFMAN(min_priority_queue* mpq,Huffman_Tree* T)中的n-1次for循環，每次for 都要做常數次維護小根堆性質的操作，每次的複雜度為O(lgn)，是以總共是：O(n+n*lgn)=O(nlgn)。