《数据结构与算法》之堆

导言：

我们在以前的学习中知道了堆栈，和队列，在系统处理上这两种数据结构的确是很高效的，但是在系统的任务调度上就是很高效了，我们cpu处理任务是有优先级的，要是按照队列和栈的思想都是线性执行，可能发生的情况就是输出一个字符比系统掉电请求处理的优先级高，可能输出一个字符先来，所以在任务调度上线性结构就会有明显的劣势，现在我们要学习的堆能否解决这一问题呢？

一.堆的相关定义和操作

什么是堆？

堆其实就是一种特殊的队列，即优先队列

它是按照已有元素的优先级来排列的，它的优先级高的在堆顶，优先级低的在堆低

堆的实现

堆的实现有很多

队列实现：本身堆就是一个优先级队列，使用队列实现可以，但是新增的元素，增删改需要大量的移动，所以不建议使用

二叉树实现：实际上我们最常用的实现就是二叉树实现，优先级高的在父结点，优先级低的在子结点，增删改比线性结构要方便的多

二叉树实现堆：

二叉树实现堆一定要满足，树是完全二叉树

如上图：

完全二叉树在除了最后一层可以有空缺外，其它层都是满的，而且最后一层的数据应该是在集中在左子树，只要同一层的左子树没有满，右子树可以没有数据

构造堆的二叉树可以不是查找二叉树，毕竟那要求太严苛了，一旦有了连续的数据肯定会导致二叉树成为线性结构，所以构造堆的时候不偏向查找二叉树，而是偏向完全二叉树

构造堆的完全二叉树应该要保证，树的父结点是大于子结点的，子结点可以无序，左节点和右结点谁大无所谓

 如上图：

这就是构建堆中的两种基本类型的堆，大顶堆和小顶堆

大顶堆：完全二叉树的情况下，父结点的值  “大于”  任一子结点

小顶堆：完全二叉树的情况下，父结点的值  “ 小于”  任一子结点

堆的有序性：

不管是大顶堆还是小顶堆，都应该满足从根结点出发，到任一子结点都是有序的（可能是递增序列，可能是递减序列）

堆的操作

选用链表的形式来实现二叉树：

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

上面就是树结点的结构：
通过 Elements 来存储元素的值

通过  Size  来记录当前的位置，以及 + 1  后下一个元素的位置

通过 Capacity  来表示堆的最大容量，用来限制堆是否可以存储，且它的默认位置数组下标的 0 号空间

 堆的插入操作（大顶堆）：

建堆前我们需要有一些准备工作，比如先把数组的0号元素作为岗哨，申请堆空间的大小，初始化堆的一些信息等等

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;
    return H;
}

上面的代码就是需要我们初始化堆的一些特性，比如存储数据的大小等等

 堆的插入特点：

• 先按照完全二叉树的结构插入新数据
• 当父结点的值小于新插入子结点时和父结点互换
• 每次互换都要向上继续检查，有可能新数据是最大的子结点

void Insert(MaxHeap H, ElementType number) {
    int i;
    if (H->Size == H->Capacity) {
        printf("堆已经满了！");
        return;
    }
    i = ++H->Size;
    for (; H->Elements[i / 2] < number; i /= 2) {
        H->Elements[i] = H->Elements[i / 2];
    }
    H->Elements[i] = number;
}

上面就是堆插入的代码：

它首先判断了堆内数组还有没有空闲的空间，如果没有了就不能插入了，反之便可以

然后就是通过循环，如果当前结点比父结点小，或者等于父结点，那么就不需要变动

如果比父结点大，那么就需要经过内循环的移动覆盖掉父结点，就是等于把父结点的元素移动到插入的子结点上，

这里需要注意的是 循环内执行的代码变量 i  和 最后把新元素赋值到结点内的  i 它们的值不是最开始的 H->Size

 堆的删除操作（大顶堆）：

堆的删除操作可以分为两步：

第一步，把要删除的元素和最后一个元素位置对调，可以采用最后一个位置直接覆盖掉要删除位置的元素，然后再断链最后一个元素

第二步，从被覆盖的位置开始，维护堆，即如果被换上来的元素小于子结点，那么就把子结点大的交换上来，继续递归知道，此结点大于子结点，或它自己是叶结点

ElementType DeleteMax(MaxHeap H) {
    int parent, child;
    ElementType MaxItem, temp;
    if (H->Size == 0) {
        printf("堆空，无需操作");
        return;
    }
    MaxItem = H->Elements[1];      //拿到最大结点
    temp = H->Elements[H->Size--]; //分号作用域内，先赋值后自减
    for (parent = 1;parent * 2 <=H->Size; parent = child)
    {
        child = parent * 2;
        //左儿子的计算方法
        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;
}

 

 上面是删除堆元素的实现：

由于删除操作都是把优先级高的删除，所以堆删除有个很明显的删除特点，就是每次删除必是删除堆顶元素

删除操作就是和最后一个元素交换，然后断链，维护

 这里我们重点来看一下堆的维护

维护有三种情况：

• 需要维护的结点本身就有两个子结点，把最大的子结点交换上来做父结点，自己去做子结点，此时需要循环此操作，又要当下一层的父结点，直到无子结点，或者自己就是最大的子结点
• 需要维护的结点本身只有一个子结点，比较这两个结点，如果子结点更大，那么就交换做父子结点，由于完全二叉树的特性，这种情况下肯定是最后一层才有的，所以交换完成就可以退出了
• 需要维护的结点本身没有子结点，这种情况就不用管它，直接退出

 堆的创建操作（大顶堆）：

创建堆的方式一共有两种：

方法一：从建堆开始，一个一个的插入元素，然后逐个的维护已构建好了的堆，它的最大创建代价是 O(N log N)，具体的操作可以参考我前面写的随笔：十大基础排序算法中的堆排序

方法二：在线性条件下，来构建大顶堆，第一步先让序列构建成完全二叉树，第二步调整结点位置，使其满足大顶堆的性质

 如上图：

使用这种方式构建堆，它是从最后一个小堆开始维护的，，然后每一层的小堆维护完成以后，就会去上一层，这样一层一层的维护

它的代码描述和上面的删除代码描述很像，可以去仿一下

二.哈夫曼树（应用型）

哈夫曼树是一种树的应用型开发，它是最多使用于编码问题，解决最多使用次数的编码在前面，最少使用的编码在后面

什么是哈夫曼树？

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

 如上图：

我们的两种编码方式，第一种是顺序编码，即按字母的先后顺序进行编码的结果，它的平均查找速率是 47

而第二种使用权值来进行编码的结果是 40，明显在相同的树结构下，第二种方式是更高的，也比较符合日常的需求

第二种就是哈夫曼树，也叫最优二叉树：WPL的值最小

WPL：带权路径长度

哈夫曼树的构造

 如上图：

哈夫曼树的构造特点是，每次构造都需要从带权序列中拿取两个最小元素作为子结点建堆，它们的父结点是两子结点的权值

父节点会被放回带权序列，继续比较后拿取两个最小的元素作为子结点建堆，然后重复以上操作

哈夫曼树应用编码

我们先来看看一个简单的编码：

我们有a，b，c，d四个字母，我们尽量少的使用二进制数字进行编码，可以怎么做呢？

a：0

b：1

c：10

d：01

我们使用的数字可能是最少的，但是编码能不能使用呢？给定一个序列 1011，它代表那些字母？

是 babb  还是  cbb  还是 bdb ，我们会很明显的发现这一串编码是有二义性的，这样的编码可能满足最少二进制数，但是不能使用

我们接下来要使用的是哈夫曼树来实现编码：

上面的编码不能使用是因为很多编码都不是前缀码。

前缀码：任何字符的编码都不是另一字符编码的前缀 （可以无二义解码）

哈夫曼树编码就满足前缀码

 上面就是使用哈夫曼树进行的编码:

它的编码格式避免了一个元素的码是另一个元素的头部的情况，实用性很强

 堆空间的应用实例可以看看我写的 Java内存模型中的堆空间，Java对堆空间在内存中做了很多优化，可以了解一下