堆,哈夫曼树及集合

堆

前面介绍过队列，它是一种先进先出的数据结构，队列中没有哪一个元素是有特权的，前面的元素未处理完，后面的只能等待。而本文章介绍的堆（Heap）正是考虑了适合于特权需求的数据结构，因此，堆也通常被称为“优先队列”（Priority Queue）。

堆的定义和表示

堆是特殊的队列，从中取出元素是依照元素的优先级大小，而不是元素进入队列的先后顺序。

那么我们应该如何组织优先队列的存储结构呢？

如采用数组或者链表实现优先队列

• 数组
  插入：元素总是插入尾部：O(1)
  删除：查找最大或最小值：O(N)
  从数组中删除需要移动元素：O(N)

• 链表
  插入：元素总是插入在链表头部：O(1)
  删除：查找最大或最小值：O(N)
  删除结点：O(1)

• 有序数组
  插入：找到合适的位置：O(N)或O(logN)
  移动元素并插入：O(N)
  删除：删除最后一个元素：O(1)

• 有序链表
  插入：找到合适的位置：O(N)
  插入元素：O(1)
  删除：删除首元素或者最后一个元素：O(1)

上面 4 种方式，其最坏时间复杂度都达到了 O(N)，而我们知道二叉搜索树的插入和删除操作代价为 O(logN)。因此我们可以利用树型结构来组织数据。

堆最常用放入结构是用二叉树表示，不特指的话，它是一颗完全二叉树。由于完全二叉树的排列及其规则，因此我们可以使用数组来实现堆的存储。

堆中的元素是按照完全二叉树的层序存储的，还需要注意的是所用数组的起始单元为 1，这样做的目的是更容易从子结点找到父结点。根据完全二叉树的性质，对于下标为 i 的结点，其父结点的下标为 [i/2]。反过来，找结点 i 的左右子结点也非常方便，分别为 2i 和 2i + 1。

堆的两个特性：

• 结构性：用数组表示的完全二叉树

• 有序性：任一结点的关键字是其子树所有结点的最大值或最小值
  在最大堆（MaxHeap）中，任一结点的值大于或等于其子结点的值，那么根元素是整个堆中最大的；
  在最小堆（MinHeap）中，任一结点的值小于或等于其子结点的值，那么根元素是整个堆中最小的。

注意：从根节点到任意节点路径上结点序列的有序性！

堆的抽象数据类型描述

以最大堆为例介绍堆的抽象数据类型描述：

类型名称：最大堆（MaxHeap）

数据对象集：完全二叉树，每个结点的元素值不小于其子结点的元素值

操作集：最大堆 H∈MaxHeap，元素 item∈ElementType，主要操作有：

• MaxHeap CreateHeap(int MaxSize)：创建长度为 MaxSize 的空最大堆

• bool IsFull(MaxHeap H)：判断最大堆是否已满

• bool Insert(MaxHeap H, ElementType X)：将元素 X 插入最大堆

• bool IsEmpty(MaxHeap H)：判断堆是否为空

• ElementType DeleteMax(MaxHeap H)：删除并返回最大元素

因此用 C 语言描述最大堆如下：

typedef int ElementType;

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

最大堆的创建

注意到根据用户的输入 MaxSize 创建最大堆时，数组应该有 MaxSize + 1 个元素，因为数组起始单元为 1，元素值存在第 1——MaxSize 个单元中。通常第 0 个单元是无用的，但是如果事先知道堆中所有元素的取值范围，也可以给第 0 个单元赋一个特殊的值 MAXDATA，这个值比堆中任何一个元素都要大。这人 MAXDATA 的“哨兵”作用会在插入操作中用到。

MaxHeap CreateHeap(int MaxSize) {
    MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
    H->Data = (ElementType*)malloc(sizeof(ElementType)*(MaxSize+1));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0] = MAXDATA;  
    return H;
}

最大堆的插入

最大堆中插入一个新元素以后，新增结点既要保证最大堆仍是一个完全二叉树，结点之间的元素值大小也要满足最大堆的性质，因此需要移动元素。

完成一个元素的最大堆插入操作，只要从完全二叉树的新增结点开始，顺着其父结点到根结点的路径，将路径上各点依次与新元素值进行比较，当一结点的值小于新元素的值，就下移这个结点的元素，直到有结点的值大于新元素的值或者根结点也下移为止，空出的结点位置就是新元素插入点。

插入过程可以用一句话简单描述：从新增的最后一个结点的父结点开始，用要插入的元素向下过滤上层结点。实际上，由于堆元素之间的部分有序性，最大堆从根结点到任一叶结点的路径都是递降的有序序列。插入过程的调整就是继续保证这个序列的有序性。

如下给出了最大堆的插入操作算法。注意到如果新插入的 X 比原先堆中所有的元素都大，那么它将一直向上比较到根结点都不会停止。对于这种情况，我们可以加一个特殊判断，当 i 值取 1 时，直接跳出循环，但是这种程序不够优美。因此之前我们定义了一个“哨兵”，即事先知道堆中所有元素的取值范围，这样可以给 H->Data[0] 赋一个特殊的值 MAXDATA，这个值比堆中所有元素都要大，这样当 i 为 1 时 H->Data[i/2] < X 这个条件肯定不满足，跳出循环。

bool IsFull(MaxHeap H) {
    return H->Size == H->Capacity;
}
bool Insert(MaxHeap H, ElementType X) {
    if(IsFull(H)){
        printf("堆已满");
        return false;
    } else {
        int i = ++(H->Size);        /* i指向插入后堆中最后一个元素 */
        for( ; H->Data[i/2] < X; i/=2)
            H->Data[i] = H->Data[i/2];  /* 上滤 X */
        H->Data[i] = X;     /* 找到位置将 X 插入 */
        return true;
    }
}

算法的时间复杂度为 O(logN)。

最大堆的删除

最大堆的删除实际上是取出根结点的最大值元素，同时删除堆的一个结点。删除后仍要是一颗完全二叉树，结点元素的大小仍要满足最大堆的性质。因此删除的结点应该是数组的最后一个单元。即取走根结点之后，最后一个结点必须重新放置。确定最后一个结点放置在哪里是最大堆删除的关键。

因此我们可以将堆中的最后一个元素当成假设的根结点，依次与下层的子结点进行比较，如果小于子结点的值，从子结点中选择较大的元素上移一层，直到在某一点上，比较结果是大于两个子结点的值，此时的空结点就是元素要放置的位置。

删除过程可用一句简单的话描述：从根节点开始，用最大堆中最后一个元素向上过滤下层结点。

bool IsEmpty(MaxHeap H) {
    return H->Size == 0;
}
ElementType Delete(MaxHeap H) {
    if(IsEmpty(H)) {
        printf("堆为空");
        return false;
    }
    ElementType MaxItem = H->Data[1];   /* 取出根结点存放最大值 */
    /* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
    ElementType X = H->Data[(H->Size)--];  /* 注意堆的规模要减1 */
    int Parent,Child;
    for(Parent=1; 2*Parent <= H->Size; Parent=Child) {
        Child = 2*Parent;   /* 先将最大儿子设为左儿子 */

        /* 如果存在右儿子，并且右儿子的值大于左儿子，则将最大儿子设为右儿子 */
        if((Child+1) <= H->Size && H->Data[Child+1] > H->Data[Child])
            Child++;
        if(X >= H->Data[Child]) break;
        else H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;

    return MaxItem;
}

其时间复杂度也为 O(logN)。

最大堆的建立

建立最大堆是指如何将已经存在的 N 个元素按照最大堆的要求存放在一个一位数组里面。主要有如下两种方法：

• 通过插入操作，将 N 个元素依次插入到一个初始为空的堆中去，其时间复杂度显然是 O(NlogN)。

• 在线性时间复杂度下建立最大堆。
  将 N 个元素按照输入顺序存入二叉树中，这一步只需要满足完全二叉树的结构特性；接着调整各结点的位置，以满足最大堆的有序特性。

我们主要介绍第二种方法：

首先将 N 个元素读入数组，接着从第 [N/2] 个结点（这是最后面一个有儿子的结点）开始，对包括此节点在内的其它前面各节点 [N/2]-1,[N-2]-2,…逐一向下进行过滤，直到根结点过滤完毕，最大堆也就建立起来了。

首先实现向下过滤的函数：

void PercDown(MaxHeap H, int p) {
    /* 对堆中的第 p 个结点向下过滤，与删除操作类似 */
    ElementType X = H->Data[p];
    int Parent,Child;
    for(Parent = p; 2*Parent <= H->Size; Parent=Child) {
        Child = 2*Parent;   /* 先将最大儿子设为左儿子 */
        /* 如果存在右儿子，并且右儿子的值大于左儿子，则将最大儿子设为右儿子 */
        if((Child+1) <= H->Size && H->Data[Child+1] > H->Data[Child])
            Child++;
        if(X >= H->Data[Child]) break;  /* 找到合适的位置 */
        else H->Data[Parent] = H->Data[Child];  /* 下滤 */
    }
    H->Data[Parent] = X;
}

接着从第 [N/2] 个结点（这是最后面一个有儿子的结点）开始，对包括此节点在内的其它前面各节点 [N/2]-1,[N-2]-2,…逐一向下进行过滤，直到根结点过滤完毕。

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

该算法的时间复杂度为 O(N)。证明如下：

哈夫曼树

首先看一个简单的例子，要求编写一个程序将百分制成绩转化成五分制成绩。首先给出一个简单的示例：

if(score < 60) grade = 1;
else if(score < 70) grade = 2;
else if(score < 80) grade = 3;
else if(score < 90) grade = 4;
else grade = 5;

其判定树如下：

如果考虑学生的成绩分布概率：

则该判定树的查找效率为：0.05x1 + 0.15x2 + 0.4x3 + 0.3x4 + 0.1x4 = 3.15

如果根据概率修改判定树：

则查找效率变为：0.05x3 + 0.15x3 + 0.4x2 + 0.3x2 + 0.1x2 = 2.2

由此可见，同一问题采用不同的判定逻辑，计算效率是不一样的。那么是否能够找到最好的比较判定逻辑，使运算效率达到最高？即如何根据结点不同的查找频率构造更有效的搜索树？

哈夫曼树的定义

带权路径长度：结点的带权路径长度是指从根结点到该结点之间的路径长度与该结点上所带权值的乘积。

设一棵树有 n 个叶子结点，每个叶结点带有权值 Wk，从根结点到每个叶结点的长度为 lk，则每个叶结点的带权路径长度之和就是这棵树的带权路径长度（Weighted Path Length,WPL），它可以表示为：

WPL = W1xl1 + W2xl2 + W3xl3 + … + Wkxlk

假设有 n 个权值构造了 n 个叶结点的二叉树，每个叶子的权重是 n 个权重之一，这样的二叉树可以构造出很多个，其中必有一个是带权路径长度最小的，这颗二叉树称为最优二叉树或哈夫曼树。

哈夫曼树的构造

由哈夫曼树和带权路径长度的定义可知，一棵二叉树要使其 WPL 最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。哈夫曼根据这一特点提出了一种方法，它是一种贪心算法。该算法在初始状态下将每个字符看成一颗独立的树，每一步执行两棵树的合并，而选择合并对象的原则是“贪心”的，即每次选择权最小的两个数进行合并。具体过程如下：

1.由给定的 n 个权值构造出 n 颗只有一个叶结点的二叉树，从而得到一个二叉树的集合 F；

2.从 F 中选取根结点的权值最小和次小的两颗二叉树作为左右子树构造出一颗新的二叉树，这棵新的二叉树根结点的权值为左右子树根结点权值之和；

3.在集合中删除上一步中作为左右子树的两颗二叉树，并将新构造的二叉树加入到集合 F 中；

4.重复2、3步，当 F 中只剩下一颗二叉树时，这颗二叉树就是所要建立的哈夫曼树。

需要注意的是：对于同一组给定权值叶结点所构造的哈夫曼树，树的形状可能不同。但无论形状如何，这些哈夫曼树的带权路径长度是相同的，并一定都是同一最小值。

为了便于抽取最小权值的子树，在构造树过程中使用最小堆的删除及插入操作。这里堆中的元素是一个加了权值的树结点的指针。

typedef struct HTNode* HuffmanTree;
struct HTNode {
    int Weight;         /* 结点权值 */
    HuffmanTree Left;   /* 指向左子树 */
    HuffmanTree Right;  /* 指向右子树 */
};
/* 定义最小堆，最小堆里面每一个元素都是一颗哈夫曼树 */
typedef struct HNode* MinHeap;
struct HNode {
    HuffmanTree *Data;
    int Size;
    int Capacity;
};

HuffmanTree Huffman(MinHeap H) {
    /* 最小堆里面的元素类型都是 HuffmanTree
       假设 H->Size 个权值已经存在 H->Data[i]->Weight 里
    */

    /* 将 H->Data[]按权值 Weight 调整为最小堆 */
    BuildHeap(H);
    int N = H->Size;
    HuffmanTree T;
    for(int i=0; i<N; i++) { /* 做 H->Size - 1次合并 */
        /* 选取两个权值最小的构建新的哈夫曼树 */
        T = (HuffmanTree)malloc(sizeof(struct HTNode)); /* 新建一个新的根结点 */
        T->Left = DeleteMin(H);                         /* 从最小堆中删除一个结点，作为 T 的左子树 */
        T->Right = DeleteMin(H);                        /* 从最小堆中删除一个结点，作为 T 的右子树 */
        T->Weight = T->Left->Weight + T->Right->Weight;   /* 新树的权值为两个子树权值之和 */
        /* 将 T 插入到堆中 */
        Insert(H, T);
    }
    return DeleteMin(H); /* 最小堆中最后一个元素即是指向哈夫曼树根结点的指针 */
}

由上可知，Huffman 算法的时间复杂度为 O(NlogN)。

哈夫曼树的特点：

• 没有度为 1 的结点；

• n 个叶子结点的哈夫曼树共有 2n-1 个结点；

• 哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树；

• 对于同一组权值，存在不同构的两颗哈夫曼树。
  如权值{1,2,3,3}，不同构的两颗哈夫曼树如下：

  

哈夫曼编码

问题：给定一段字符串，如何对其中的字符进行编码，使得该字符串的编码存储空间最少？当然从存储空间取出的编码必须通过对应的解码才能还原出字符串。

上述问题的最优解决方法是哈夫曼提出的，按他给出的算法得到的编码就称为“哈夫曼编码”，是进行文件压缩的有效方法，其压缩比通常在 20% 到 90%。

可见的 ASCII 字符大约有一百个左右，加上部分不可见字符，可以用 7 位来识别它们，再加上 1 位校验码，所以一般用 8 位即一个字节来表示一个字符。但在一般的文本中每个字符出现的频率是不同的，且差异较大，通常只是少量不同字符在大量重复出现，用 8 位来存储每个字符是比较浪费的。

假设有一段文本，包含 58 个字符，并由以下 7 个字符构成：a,e,i,s,t,空格(sp),换行(nl)；这 7 个字符出现的次数不同。如何对这 7 个字符进行编码，使得总编码空间最少。

分析：

• 采用等长 ASCII 编码：58x8 = 464 位；

• 仔细分析里面只有 7 个字符是不同的，因此我们完全可以用等长 3 位编码来识别它们。例如可令 a=000,e=001,i=010,s=011,t=100,sp=101,nl=110。这时空间为 58x3 = 174 位；

• 采用不等长编码：出现频率高的字符用的编码短些，出现频率低的字符则可以编码长些。

因此我们需要解决两个问题：怎么进行不等长编码？如何避免编码的二义性？

不等长编码实际上就是根据字符出现的概率进行编码。

定义 前缀码：任何字符的编码都不是另一个字符编码的前缀。

为了避免二义性，所有字符都有应该在二叉树的叶结点上，哈夫曼编码也称为前缀编码。

因此采用哈夫曼树的生成方法可以满足以上要求。

集合及其运算

集合是一种常用的数据表示方法。集合的运算包括交、并、补、差以及判定一个数据是否是某一集合中的元素。

为了有效地对集合执行各种操作，可以用树结构表示集合，树的每个结点代表一个集合元素。

我们也可以采用数据形式存储集合，数组的每一项是一个结构体，结构体里面是元素值，以及其父元素对应的数组下标，负数代表根节点，非负数代表其父元素的数组下标。

因此可以定义如下结构体来表示集合：

#define MAXSIZE 1000    /* 集合的最大容量 */
typedef int ElementType;
typedef struct {
    ElementType Data;
    int Parent;
} SetType;

1.查找元素所在集合（用根结点表示）

int Find(SetType S[], ElementType X) {
    /* 在数组 S 中查找值位 X 的元素所属集合
       MAXSIZE 为数组 S 的最大长度
    */
    int i;
    for(i=0; i<MAXSIZE && S[i].Data!=X; i++);
    if(i==MAXSIZE)  return -1; /* 未找到 X，返回 -1 */
    /* 找到 X，则查找其父结点，直到父结点为负数 */
    for(; S[i].Parent>=0; i=S[i].Parent);
    return i;   /* 找到 X 所属集合，返回根结点在数组 S 中的下标 */
}

2.集合的并运算

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

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

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

当我们进行两个集合的合并时，我们希望合并后的集合树的深度尽可能小，这样才能提高查找效率。因此如果每次合并都能比较以下树的高矮，将矮树合并到高树上，这样就能有良好的查找效率。

当然要做到这一点，我们需要知道每个集合的树的高度，而这并不是很容易做到。比较容易获得的是集合当前的元素个数，用个数替换高度也可以起到比较好的作用。这种按照规模或者按照高度合并的算法，统称为按“秩”合并。

因此我们可以把对应集合的树的总结点数存在根结点单元里，同时在它前面加上符号。因此对上面的代码进行改写之后有：

void Union(SetType S[], ElementType X1, ElementType X2) {
    int Root1 = Find(S,X1);
    int Root2 = Find(S,X2);

    if(Root1 != Root2){
        /* 将元素少的集合合并到元素多的集合中，集合中元素个数用的负数表示 */
        if(S[Root1].Data > S[Root2].Data) {
            S[Root1].Parent = Root2;
            S[Root2].Data += S[Root1].Data; /* 更新集合中元素个数 */
        } else {
            S[Root2].Parent = Root1;
            S[Root1].Data += S[Root2].Data;
        }

    }
}