Scott's world.

第五讲树下

Word count: 1.5kReading time: 6 min
2019/07/26 Share

第五讲 树(下)

5.1 堆

优先队列

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

堆的抽象数据类型描述

1
2
3
4
5
6
7
//伪代码
typedef struct HeapStruct * MaxHeap;
struct HeapStruct{
ElementType * Elements;
int Size; //堆当前元素个数
int Capacity;//堆的最大容量
};

最大堆的操作

创建

1
2
3
4
5
6
7
8
9
//伪代码
MaxHeap Create(int MaxSize)
{
MaxHeap H=malloc(sizeof(struct HeapStruct));
H->Elements = malloc((MaxSize+1) * sizeof(ElementType));
H->Size = 0;
H->Capacity = MaxSize;
H->Elements[0] = MaxData; //定义为哨兵为大于堆中所有可能元素的值
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
//伪代码
void Insert(MaxHeap H,ElementType item)
{
int i;
if(IsFull(H)){
cout<<"最大堆已满"<<endl;
return ;
}
i = ++ H->Size; //i指向插入后堆中的最后一个元素的位置
for(;H->Elements[i/2] < item && i>1 ; i/=2)
H->Elements[i] = H->Elements[i/2]; //int除法向下取整
H->Elements[i] = item ; //该过程类似于插入排序
}

删除

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ElementType DeleteMax(MaxHeap H)
{
//从最大堆H中取出键值为最大的元素,并删除一个结点
int Parent,Child;
ElementType MaxItem,temp;
if(IsEmpty(H)){
cout<<"最大堆已空"<<endl;
return;
}
MaxItem = H->Elements[1]; //取出根结点
temp = H->Elements[H->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++; //比较左右孩子大小
if(temp>=H->Elements[Child]) break;
else
H->Elements[Parent] = H->Elements[Child];
}
H->Elements[Parent] = temp;
return MaxItem;
}

建立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void PrecDown(MaxHeap H,int p)
{
//下滤:将H中以H->Data[p]为根的子堆调整为最大堆
int Parent ,Child;
ElementType X;

X = H ->Data[p]; //取出根结点存放的值
for(Parent = p;Parent*2<=H->Size;Parent=Child)
{
Child=Parent * 2;
if((Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]))
Child++; //Child指向左右子结点的较大值
if(X>=H->Data[Child]) break; //找到合适的位置
else //下滤
H->Data[Parent] = H->Data[Child];
}
H->Data[Parent] = X;
}

void BuildHeap (MaxHeap H)
{
//调整H->Data[]中的元素,使满足最大堆的有序性
//这里假设所有H->Size个元素已经存在H->Data[]中
int i ;
//从最后一个结点的父节点开始,到根结点1
for(i=H->Size/2;i>0;i--)
PercDown(H,i);
}

5.2 哈夫曼树与哈夫曼编码

哈夫曼树的定义

哈夫曼树的构造

  • 每次把权值最小的两颗二叉树合并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//伪代码
//时间复杂度O(NlogN)
typedef struct TreeNode * HuffmanTree;
struct TreeNode{
int Weight;
HuffmanTree Left,Right;
}
HuffmanTree Huffman(MinHeap H)
{
/* 假设H->Size个权值已经存在H->Elements[]->Weight里 */
int i;
HuffmanTree T;
BuildMinHeap(H);//将H->Elements[]按权值调整为最小堆
for(i = 1;i<H->Size;i++) //做H->Size-1次合并
{
T = malloc(sizeof(struct TreeNode)); //建立新结点
T->Left=DeleteMin(H); //从最小堆中删除一个结点,作为新T的左子节点
T->Right=DeleteMin(H);//从最小堆中删除一个结点,作为新T的右子结点
T->Weight=T->Left->Weight+T->Right->Weight;
Insert(H,T); //将新T插入最小堆
}
T=DeleteMin(H);
return T;
}

特点

  • 没有度为1的结点
  • n个叶子结点的哈夫曼树共有2n-1个结点
  • 哈夫曼树任意非叶结点的左右子树交换后仍是哈夫曼树
  • 对同一组权值{w1,w2,…..,wn},可能有不同构的两棵哈夫曼树,但WPL始终相同

哈夫曼编码

给定一段字符串,如何对字符进行编码,可以使得该字符串的编码存储空间最少

  • ASCII
  • 等长编码
  • 不等长编码

前缀码

任何字符的编码都不是另一字符编码的前缀

可以无二义地编码

  • 若使用二叉树进行编码

    1.左右分支:0,1

    2.字符只出现在叶子结点上

例 哈夫曼编码

5.3 集合及运算

集合的表示

  • 可以用树结构表示结合,树的每个结点代表一个集合元素

双亲表示法:孩子指向双亲

  • 采用数组存储形式

集合运算

查找某个元素所在集合

  • 用根结点表示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //伪代码
    int Find(SetType S[],ElementType X)
    {
    //在数组S中查找值为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);
    return i;
    }

集合的并运算

  • 分别找到X1和X2两个元素所在集合树的根结点

  • 如果它们不同根,则将其中一个根结点的父节点指针设置成另一个根结点的数组下标

    1
    2
    3
    4
    5
    6
    7
    8
    //伪代码
    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;
    }

比如可以将根结点的Parent值改为该集合的个数

例题

堆中的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#define MAXN 1001
#define MINH -10001

int H[MAXN],size;

vodi Create()
{
size=0;
H[0]=MINH;
}

void Insert(int X)
{
int i;
for(i=++size;H[i/2]>X;i/=2)
{
H[i]=H[i/2];
}
H[i]=X;
}

int main()
{
int n,m,x,i,j;
scanf("%d %d",&n,&m);
Create();
for(i=0;i<n;i++)
{
scanf("%d",&x);
Insert(x);
}
for(i=0;i<m;i++)
{
scanf("%d",&j);
printf("%d",H[j]);
while(j>1)
{
j/=2;
printf(" %d",H[j]);
}
printf("\n");
}
return 0;
}

File Transfer

集合的简化表示

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef int ElementType;
typedef int SetName;
typedef ElementType SetType[MaxSize];

SetName Find(SetType S,ElementType X)
{
for(;S[X]>=0;X=S[X]);
return X;
}
void Union(SetType S,SetName Root1,SetName Root2)
{
S[Root2]=Root1;
}

题意理解

解答分析

程序框架搭建

按秩归并
  • 比高度

  • 比规模

路径压缩

CATALOG
  1. 1. 第五讲 树(下)
    1. 1.1. 5.1 堆
      1. 1.1.1. 优先队列
      2. 1.1.2. 堆的抽象数据类型描述
      3. 1.1.3. 最大堆的操作
        1. 1.1.3.1. 创建
        2. 1.1.3.2. 插入
        3. 1.1.3.3. 删除
        4. 1.1.3.4. 建立
    2. 1.2. 5.2 哈夫曼树与哈夫曼编码
      1. 1.2.1. 哈夫曼树的定义
      2. 1.2.2. 哈夫曼树的构造
        1. 1.2.2.1. 特点
      3. 1.2.3. 哈夫曼编码
        1. 1.2.3.1. 前缀码
    3. 1.3. 5.3 集合及运算
      1. 1.3.1. 集合的表示
      2. 1.3.2. 集合运算
        1. 1.3.2.1. 查找某个元素所在集合
        2. 1.3.2.2. 集合的并运算
    4. 1.4. 例题
      1. 1.4.1. 堆中的路径
      2. 1.4.2. File Transfer
        1. 1.4.2.1. 集合的简化表示
        2. 1.4.2.2. 题意理解
        3. 1.4.2.3. 解答分析
          1. 1.4.2.3.1. 程序框架搭建
          2. 1.4.2.3.2. 按秩归并
          3. 1.4.2.3.3. 路径压缩