ZJU 数据结构课程笔记 | 堆

这是我在学习浙江大学 MOOC『数据结构』的第四章：堆 的过程中做的笔记。

ZJU 数据结构 MOOC 课程链接

什么是堆

def 优先队列(Priority Queue): 特殊的队列, 取出元素的顺序是依照元素的优先权(关键字)大小, 而不是元素进入队列的先后顺序

能否采用二叉树存储结构

二叉搜索树
如果采用二叉树结构, 应该更关注插入还是删除
- 树结点顺序怎么安排
- 树结构怎么样

结构性 & 有序性

最大堆及其实现

最大堆的创建

建立最大堆: 将已经存在的N个元素按最大堆的要求存放再一维数组中.

通过插入操作, 将N个元素一个个相继插入到一个初始为空的堆中去, 其时间代价最大为.
在线性时间复杂度下建立最大堆

(1) 将N个元素按输入顺序存入, 先满足完全二叉树的结构特性.
(2) 调整各结点位置, 以满足最大堆的有序特性.

typedef struct HeapStruct *MaxHeap;
struct HeapStruct {
	ElementType *Elements; //存储堆元素的数组
	int Size; //堆的当前元素个数
	int Capacity; //堆的最大容量
};

MaxHeap Create(int MaxSize)
{
	MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapStruct));
	H -> Elements = (ElementType *)malloc((MaxSize + 1) * 
	sizeof(ElementType));
	H -> Size = 0;
	H -> Capacity = MaxSize;
	H -> Elements[0] = MaxData;
	return H;
}

function insert

新增结点插入到从其父节点到根节点的有序序列中

void Insert(MaxHeap H, ElementType item)
{ //item插入最大堆H,其中H -> Elements[0]已经定义为哨兵
	int i;
	if (isFull(H)) {
		printf("the Heap is full!");
		return ;
	}
	i = ++ H -> Size; //i指向插入后堆中的最后一个元素位置
	for (; H -> Elements[i / 2] < item; i /= 2)
		H -> Elements[i] = H -> Elements[i / 2]; //向下过滤结点
	H -> Elements[i] = item; //item插入
}

function delete

取出根节点(最大值)元素, 同时删除堆的一个结点

ElementType DeleteMax(MaxHeap H)
{
	//从最大堆H中取出键值最大的元素, 并删除一个结点
	int Parent, Child;
	ElementType MaxItem, temp;
	if (IsEmpty(H)) {
		printf("the heap is empty");
	}
	MaxItem = H -> Elements[1]; //取出根节点最大值
	//用最大堆中最后一个元素从根节点开始向上过滤下层结点
	temp = H -> Elements[H -> Size --];
	//取出temp后Size由于删除元素须进行自减
	for (Parent = 1; Parent * 2 <= H -> Size; Parent = Child) {
		Child = Parent * 2; //child取左儿子
		if ((Child != H -> Size)) &&
			(H -> Elements[Child] < H -> Elements[CHild + 1])
			Child ++; //Child指向左右子结点的较大者
		if (temp >= H -> Elements[Child]) break;
		else //移动temp元素到下一层
			H -> Elements[Parent] = H -> Elements[Child];
	}
	H -> Elements[Parent] = temp;
	return MaxItem;
}

哈夫曼树与哈夫曼编码

注意到, 利用搜索树进行搜索时, 各结点不同的查找频率会影响整棵树的查找效率.

根据结点不同的查找频率构造更有效的搜索树.

def 带权路径长度(WPL): 设二叉树有个叶子结点, 每个叶子结点带有权值, 从根结点到每个叶子结点的长度为, 则每个叶子结点的带权路径长度和为.

def 哈夫曼树(最优二叉树): WPL最小的二叉树.

哈夫曼树的构造

每次把权值最小的两棵二叉树合并

typedef struct TreeNode *HuffmanTree;
struct TreeNode {
	int Weight;
	HuffmanTree Left, Right;
};
HuffmanTree Huffman(MinHeap H)
{
	int i; HuffmanTree T;
	BuildMinHeap(H); //创建最小堆
	for (i = 1; i < H -> Size; i ++) {
		T = (HuffmanTree)malloc(sizeof(struct TreeNode));
		T -> Left = DeleteMin(H);
		T -> Right = DeleteMin(H);
		T -> Weight = T -> Left -> Weight+T -> Right -> Weigth;
		Insert(H, T);
	}
	T = DeleteMin(H);
	return T;
}

哈夫曼树的特点

没有度为1的结点(不存在一子树情况).
n个叶结点的哈夫曼树共有个结点.
哈夫曼树的任意非叶结点的左右子树交换后仍时哈夫曼树.
对同一组权值{}, 可能存在不同构的两棵哈夫曼树.

哈夫曼编码

在数据传送时，信息表现为0和1的二进制形式. 为了提高传输的速, 可以采用变长的编码方式, 寻找更优的编码方式. 同时, 必须要保证编码不存在二义性（无歧义解码, 任意字符编码都不是其它字符编码的前缀.

哈夫曼编码就是符合上述要求的编码方式, 采用自底向上的形式构造哈夫曼树. 按照字符的概率分配码长, 实现平均码长最短的编码.

用二叉树进行编码

左右分支: 0, 1.
==字符只在叶结点上==

构造哈夫曼树进行编码

集合

集合的表示

集合运算
并查集

typedef struct {
	ELementType Data; //集合元素
	int Parent; //父节点位置
} SetType;

并查集集合存储实现:

利用树结构表示集合, 树的每个结点代表一个集合元素.
数组存储形式.

集合运算

(1) 查找一个元素所在的集合(根结点表示)

int Find(SetType S[], ElementType X)
{
	int i;
	for (i = 0; i < MaxSize && S[i].Data != X; i ++) ;
	if (i >= MaxSize) return -1;
	for (; S[i].Parent >= 0; i= S[i].Parent) ;
	//每循环一次, i的值更新为其父节点的值
	return i;// 返回根结点下标
}

(2) 集合的并运算

void Union(SetType S[], ElementType X1, ElementType X2)
{
	int Root1, Root2;
	Root1 = Find(S, X1);
	Root2 = Find(S, X2);
	if (Root1 != Root2) S[Root2].Parent = Root1;
	return ;
}

为了改善集合合并后的查找性能, 一般将小集合并入大集合中(按秩归并)

实现: 将 $集合元素数量$ 赋值给根结点的Parent.

集合的简化表示

typedef int ElementType ;
typedef int SetName;
typedef ElementType SetType[MaxSize];
SetName Find(SetType S, ElementType X)
{//默认元素全部初始化为-1
	for (; S[X] >= 0; X = S[X]);
	retrun X;
}
void Union(SetType S, SetName Root1, SetName Root2)
{//默认Root1和Root2时不同集合的根结点
	S[Root2] = Root1;
	return ;
}

求并集时的按秩归并思想

防止集合树越来越高, 使得查找时间复杂度大大增加.

解决方案: 将矮树根结点并入高树根结点 – 小集合并入大集合.

树的高度存在哪?

(1) 按树高归并

S[root] = $集合树的高度$ . (树高的相反数)

void Union(SetType S[], ElementType X1, ElementType X2)
{
	int Root1, Root2;
	Root1 = Find(S, X1);
	Root2 = Find(S, X2);
	if (S[Root1] > S[Root2]) //Root1树高小于Root2
		S[Root1] = Root2; //将Root1并入Root2
	else {
		if (S[Root1] == S[Root2]) S[Root1] --;
		S[Root2] = Root1;
	}
	return ;
}

(2) 按规模归并

S[root] = $集合元素数量$ . (元素数的相反数)

void Union(SetType S, SetName Root1, SetName Root2)
{
	if (S[Root2] < S[Root1]) {
		S[Root2] += S[Root1];
		S[Root1] = Root2; //Root2元素多, Root1并入Root2
	} else {
		S[Root1] += S[Root2];
		S[Root2] = Root1;
	}
	return ;
}

集合查找的路径压缩优化

SetName Find(SetType S, ElementType X)
{
	if (S[X] < 0) return X;
	else return S[X] = Find(S, S[X]);
}