最小堆和哈夫曼树的建立

2023-12-11 13:14:45

浙大数据结构

堆用完全二叉树的结构形式组织存储，表现为结构性，任一结点的关键字是其所有子树结点的最大值（称这样的堆为最大堆）或者最小值（称这样的堆为最小堆），表现为有序性。
最小堆和哈夫曼树的建立
可以按从上往下，从左到右的顺序排序，把二维结构的完全二叉树转换成一维结构的数组进行存储。通过下标进行访问时，任意父结点的下标正好是其左右儿子结点的二分之一倍。
最小堆和哈夫曼树的建立

最小堆的建立

以数组的形式存储了一组数据来表示完全二叉树后，先满足了最小堆的结构性，然后通过调整结点数据才满足最小堆的有序性。
最小堆和哈夫曼树的建立

通过已使用的最后一个数组单元下标访问其父结点，该父结点就是最后一个有儿子的结点，往后都是叶子结点。从最后一个父结点开始往前调整使每一棵子树都满足有序性。
最小堆和哈夫曼树的建立

/* 最小堆的建立 */
void BuilMinHeap(MinHeap *H){
	/* BuilMinHeap()使用DeleteMin()相似原理 */
	/* 调整元素使其满足有序性 */ 
	int i;
	i = H->Size/2;
	for(i; i>=1; i--){
		DHeap(H, i);
	} 
} 
void DHeap(MinHeap *H, int p){
    int Parent, Child;
    ElementType temp;
    temp = H->Elements[p]; //取出根结点 
    for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
        Child = Parent * 2;
        if(Child != H->Size && 
		H->Elements[Child]->Weight > H->Elements[Child+1]->Weight)
            Child++;  //Child指向左右子结点的权值较小者 
        if( temp->Weight <= H->Elements[Child]->Weight ) break; //找到了合适位置 
        else H->Elements[Parent] = H->Elements[Child];
    }
    H->Elements[Parent] = temp;
}

弹出（删除）结点

建成最小堆后弹出权值最小结点（根结点）与最小堆的建立使用的方案非常相似。每次弹出根节点后使用最后一个叶子结点填充根节点，再向下过滤寻找适合的位置进行存储。
最小堆和哈夫曼树的建立

/* 弹出(删除)结点 */ 
ElementType DeleteMin(MinHeap *H){
	ElementType MinItem, temp;
	int Parent, Child;
	if(H->Size == 0){
		cout << "堆空！" << endl;
		return NULL;
	}
	MinItem = H->Elements[1];
	temp = H->Elements[H->Size--];
	for(Parent=1; Parent*2<=H->Size; Parent=Child){
		Child = Parent * 2;
		if(H->Size != Child && 
		H->Elements[Child]->Weight > H->Elements[Child+1]->Weight){
			Child++;
		}
		if(temp->Weight <= H->Elements[Child]->Weight) break;
		else H->Elements[Parent] = H->Elements[Child];
	}
	H->Elements[Parent] = temp;
	return MinItem;
}

插入结点

在当前最小堆的最后一个结点的下一个数组单元插入后，再向下过滤找到合适的真正位置。
最小堆和哈夫曼树的建立

/* 插入新节点 */ 
void Insert(MinHeap *H, ElementType item){
	int i;
	if(H->Size == H->Capacity){
		cout << "堆满！" << endl;
		return ;
	}
	i = ++H->Size;
	H->Elements[0]->Weight = item->Weight;//哨兵 
	for(i ; item->Weight < H->Elements[i/2]->Weight; i=i/2){//比较哈夫曼树权值 
		H->Elements[i] = H->Elements[i/2];
	}
	H->Elements[i] = item; 
	
	for(int i=1; i<=H->Size; i++)
		cout <<  H->Elements[i]->Weight << ' ';
	cout << endl;
}

哈夫曼树的建立

通过已经建成的最小堆，两次次弹出（删除）堆内一个根节点（最小值）两个权值相加得到一个新的结点，再插回最小堆。以此循环最终最小堆内只存在一个根节点，即哈夫曼树的根节点。

这里得到的树完全以数据结构的形式进行存储，左右孩子通过指针连接而不再以数组下标查找。
最小堆和哈夫曼树的建立

完整代码（我粗浅的理解如有不足或表述不清，还望指出。）

#include <iostream>
#include <cstdlib>
#include <queue>

using namespace std;

typedef struct TreeNode{
	int Weight;//权值  /* 比较哈夫曼树权值 */
	struct TreeNode *Left, *Right;
}HuffmanTree;
typedef HuffmanTree * ElementType;//元素类型为哈夫曼树的结点指针 
typedef struct HeapStruct{
	ElementType *Elements;//堆存储元素的数组，而元素类型为哈夫曼树的结点指针 
	int Size;//堆的当前元素个数 
	int Capacity;//堆的最大容量 
}MinHeap;

void LevelOrderTraversal(HuffmanTree *T);
MinHeap *Create(int MaxSize);
void Insert(MinHeap *H, ElementType item);
ElementType DeleteMin(MinHeap *H);
void DHeap(MinHeap *H, int p);
void BuilMinHeap(MinHeap *H);
HuffmanTree *Huffman(MinHeap *H);

int main(){
	MinHeap *H;
	HuffmanTree *T;
	int MaxSize = 10;
	H = Create(MaxSize);
	/* 指针数组，每个元素的指针类型为HuffmanTree* */
	/* 为权值Weight附初始值 */
	for(int i=1; i<=MaxSize; i++){
		cin >> H->Elements[i]->Weight;
		H->Size++;
	}
	T = Huffman(H);
	LevelOrderTraversal(T);
	
	return 0;
}
/* 哈夫曼树的建立
   用最小堆辅助实现 */
HuffmanTree *Huffman(MinHeap *H){
	int i;
	HuffmanTree *T;
	/* 建立最小堆 */ 
	BuilMinHeap(H);
	for(i=1; i<H->Size; i){
		T = (HuffmanTree *)malloc(sizeof(HuffmanTree));
		T->Left = T->Right = NULL;
		T->Left = DeleteMin(H);//取出两个权值最小的结点 
		T->Right = DeleteMin(H);
		T->Weight = T->Left->Weight + T->Right->Weight;//合并权值 
		Insert(H, T);//插回最小堆 
	}
	T = DeleteMin(H);
	return T;
}
/* 最小堆的建立 */
void BuilMinHeap(MinHeap *H){
	/* BuilMinHeap()使用DeleteMin()相似原理 */
	/* 调整元素使其满足有序性 */ 
	int i;
	i = H->Size/2;
	for(i; i>=1; i--){
		DHeap(H, i);
	} 
} 
void DHeap(MinHeap *H, int p){
    int Parent, Child;
    ElementType temp;
    temp = H->Elements[p]; //取出根结点 
    for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
        Child = Parent * 2;
        if(Child != H->Size && 
		H->Elements[Child]->Weight > H->Elements[Child+1]->Weight)
            Child++;  //Child指向左右子结点的权值较小者 
        if( temp->Weight <= H->Elements[Child]->Weight ) break; //找到了合适位置 
        else H->Elements[Parent] = H->Elements[Child];
    }
    H->Elements[Parent] = temp;
}
/* 弹出(删除)结点 */ 
ElementType DeleteMin(MinHeap *H){
	ElementType MinItem, temp;
	int Parent, Child;
	if(H->Size == 0){
		cout << "堆空！" << endl;
		return NULL;
	}
	MinItem = H->Elements[1];
	temp = H->Elements[H->Size--];
	for(Parent=1; Parent*2<=H->Size; Parent=Child){
		Child = Parent * 2;
		if(H->Size != Child && 
		H->Elements[Child]->Weight > H->Elements[Child+1]->Weight){
			Child++;
		}
		if(temp->Weight <= H->Elements[Child]->Weight) break;
		else H->Elements[Parent] = H->Elements[Child];
	}
	H->Elements[Parent] = temp;
	return MinItem;
}
/* 插入新节点 */ 
void Insert(MinHeap *H, ElementType item){
	int i;
	if(H->Size == H->Capacity){
		cout << "堆满！" << endl;
		return ;
	}
	i = ++H->Size;
	H->Elements[0]->Weight = item->Weight;//哨兵 
	for(i ; item->Weight < H->Elements[i/2]->Weight; i=i/2){//比较哈夫曼树权值 
		H->Elements[i] = H->Elements[i/2];
	}
	H->Elements[i] = item; 
} 
/* 申请空间 */
MinHeap *Create(int MaxSize){
	MinHeap *H = (MinHeap *)malloc(sizeof(MinHeap));
	H->Elements = (ElementType *)malloc((MaxSize+1) * sizeof(ElementType));
	/* 为指针数组内每个元素指针申请内存空间 */
	for(int i=0; i<MaxSize+1; i++){
		H->Elements[i] = (ElementType )malloc(sizeof(HuffmanTree));
		H->Elements[i]->Left = H->Elements[i]->Right =NULL;
	}
	H->Size = 0;
	H->Capacity = MaxSize;
	//H->Elements[0] = MaxData; 哨兵 
	return H; 
}

/* 树的层次遍历 */ 
void LevelOrderTraversal(HuffmanTree *T){
	HuffmanTree *temp;
	queue<HuffmanTree *> S;
	S.push(T);
	while(!S.empty()){
		temp = S.front();//取出指针结点，该结点仍然在队列中 
		S.pop();//真正弹出 但无返回值 
		cout << temp->Weight << ' ';
		if(temp->Left)
			S.push(temp->Left);
		if(temp->Right)
			S.push(temp->Right);
	}
	cout << endl;
}
上一篇：AAC----wav格式


下一篇：spring-boot-starter-parent和spring-boot-dependencies的作用