优先队列

优先队列(Priority Queue)：特殊的“队列”，取出元素的顺序是依照元素的优先权(关键字)大小，而不是元素进入队列的先后顺序
问题：如何组织优先队列？

  • 一般的数组、链表？
  • 有序的数组或链表？
  • 二叉搜索树、AVL树？

优先队列的实现

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

  • 数组：
    • 插入——元素总是插入尾部——Θ(1)Θ(1)
  • 删除——查找最大(或最小)的关键字——Θ(n)Θ(n)
    • 从数组中删去关键字需要移动其他元素——Θ(n)Θ(n)
  • 链表：
    • 插入——元素总是插入链表的头部——Θ(1)Θ(1)
    • 删除——查找最大(或最小)关键字——Θ(n)Θ(n)
      • 删去结点——Θ(1)Θ(1)
  • 有序数组：
    • 找到合适的位置——O(n)O(n)或O(log2n)O(log_2n)
      • 移动元素并插入——O(n)O(n)
    • 删去最后一个元素(最大或最小)——Θ(1)Θ(1)
  • 有序链表：
    • 插入——找到合适的位置——O(n)O(n)
      • 插入元素——Θ(1)Θ(1)
    • 删除——删除首元素或尾元素——Θ(1)Θ(1)

问题：是否可以采用二叉树存储结构？

  • 使用二叉搜索树？

    • 可以采用二叉搜索树，但是二叉搜索树在删除结点后不会对树的高度进行调整(注意是不带平衡操作版本的)
    • 所以在删除多个最大(最小)元素后树的形态就歪掉了

  • 如果采用二叉树结构，应更关注插入还是删除？

    • 树结点顺序如何安排？
    • 树是怎样的结构？

优先队列的完全二叉树表示——堆

堆的定义

堆(Heap)：两个特性

  • 结构性：用数组表示的完全二叉树存储(此处特指二叉堆)
  • 有序性：任一结点的关键字是其子树所有结点的最大值(或最小值)
    • “最大堆(MaxHeap)”，也称“大顶堆”：根结点是最大值
    • “最小堆(MinHeap)”，也称“小顶堆”：根结点是最小值
  • 注意，从根结点到任一结点的路径上结点序列的有序性

堆的抽象数据类型描述

类型名称：最大堆(MaxHeap)
数据对象集：完全二叉树，每个结点的元素值不小于其子结点的元素值
操作集：最大堆H ∈ MaxHeap，元素item ∈ ElementType，主要操作有：
MaxHeap Create(int MaxSize):创建一个空的最大堆;
Boolean IsFull(MaxHeap H):判断最大堆H是否已满;
Insert(MaxHeap H,ElementType item):将元素item插入最大堆H;
Boolean IEmpty(MaxHeap H):判断最大堆H是否为空;
ElementType DeleteMax(MaxHeap H):返回H中最大元素(高优先级);

堆的顺序存储实现(以最大堆为例)

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

堆的实现(以最大堆为例)

堆的创建(空堆)

MaxHeap Create(int MaxSize)                                 //创建容量为MaxSize的空的最大堆
{
    MaxHeap H=(MaxHeap)malloc(sizeof(struct HeapStruct));
    H->Elements=(ElementType*)malloc((MaxSize+1)*sizeof(ElementType));//因为堆的元素从下标为1开始存放所以申请MaxSize+1
    H->Size=0,H->Capacity=MaxSize,H->Elements[0]=MaxData;   //定义“哨兵”为a大于堆中所有可能元素的值，便于以后更快操作
    //哨兵元素在堆中的必要性：因为堆元素在插入时会一直向上比较，当比较到根结点的时候如果没有哨兵元素就会发生越界
    return H;
}

将其中的MaxData换成小于对中所有元素的MinData，同样适用于创建最小堆

堆的插入

最大堆的插入算法：将新增结点插入到从其父结点到根结点的有序序列中
时间复杂度：T(N)=O(logN)T(N)=O(logN)

void Insert(MaxHeap H,ElementType item)
//将元素item插入最大堆H，其中H->Elements[0]已经定义为哨兵
//哨兵元素不小于堆中的最大元素，控制循环顺利结束
{
    int i;
    if(IsFull(H)){
        cout<<"最大堆已满"<<endl;
        return;
    }
    i=++H->Size;                                           //i的初值为最大堆中当前最后一个元素的后一个位置
    for(;item>H->Elements[i/2];i/=2)  //将item值与Elements[i]所在子树的根结点进行比较，如果大的话继续向上比较(将i移到i/2)
        H->Elements[i]=H->Elements[i/2];//同时如果item比根结点就将根结点移到i的位置(向下过滤结点)，比逐个交换数据效率高
    H->Elements[i]=item;                                   //循环跳出后，将item插入i当前位置
}

循环条件改为item<H->Elements[i/2]就是最小堆插入

堆的删除

最大堆的删除算法：取出根结点(最大值)元素，同时取堆的最后一个结点(为了保持完全二叉树的结构特性)
将其移动到根结点处，找出根结点最大的孩子与其进行比较，如果比根结点大就交换两个结点，直到根结点关键字比所有孩子都大
时间复杂度：T(N)=O(logN)T(N)=O(logN)

ElementType DeleteMax(MaxHeap H)
{
    int Parent,Child;
    ElementType MaxItem,temp;
    if(IsEmpty)
    {
        cout<<"最大堆已为空"<<endl;
        return -1;
    }
    MaxItem=H->Elements[0];                               //取出根结点最大值
    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++;//Child==H->Size说明左孩子是最后的元素
        if(temp>=H->Elements[Child])break;                //当temp大于两个孩子时跳出循环
        else H->Elements[Parent]=H->Elements[Child];      //移动temp元素到下一层
    }
    H->Elements[Parent]=temp;//将temp的值赋给当前位置(此时该位置的值一定是无效的，因为之前的结点要么被删除，要么移到了上层结点)
    return MaxItem;
}

堆的建立

最大堆的建立
堆的一个很重要的应用——堆排序

  • 需要建立最大(最小)堆

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

  • 算法1(自顶向下)：通过插入操作，将N个元素一一相继插入到一个初始为空的堆中去
    • 其最大时间代价为O(NlogN)O(NlogN)
  • 算法2(自底向上)：在线性时间复杂度O(N)O(N)下建立最大堆
    • 核心思想：借鉴删除操作中调整堆的方法
      • 在删除中是在左右子树都已经是堆的情况下调整根结点
      • 因此，创建堆的过程可以反过来，从叶子结点往上开始调整根结点，保证下面的都是堆，然后再向上调整
    • 将N个元素按输入顺序存入，先满足完全二叉树的结构特性
    • 调整结点位置(使用类似删除结点中的下滤调整算法，从根结点依次向下调整)，已满足最大堆的有序特性
    • 建堆从Size/2开始，即第一个非叶结点开始建堆，倒数第二层需要比较1次，倒数第三层需要比较2次……直到根结点需要比较lgN次
      • T(N)=N/4+2N/8+…+2(lgN−1)+lgNT(N)=N/4+2N/8+…+2(lgN-1)+lgN
        • T(N)=N/4+2N/8+…+2(h−2)+h−1T(N)=N/4+2N/8+…+2(h-2)+h-1
      • 由错位相减法
        • $2T(N)-T(N)=N/2+N/4+N/8+…+2-(h-1)< N-lgN+1< N $
      • 因此，该算法复杂度为O(N)O(N)
    • 此时在一棵调整好的堆上，不同层数h的结点对应的最多交换次数为
层数 结点数 最多交换次数
11 11 lgNlgN
22 22 lgN−1lgN-1
…… …… ……
lgNlgN N/4N/4 1
lgN+1lgN+1 N/2N/2 0

自底向上算法建立最大堆

void PercDownBuild(MaxHeap H)
{
    int Parent,Child;
    ElementType temp;
    for(int i=H->Size/2;i>=1;i--)
    {
        temp=H->Elements[i];                             
        for(Parent=i;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;
    }
}

堆的实现演示

//浙江大学mooc数据结构
#include <cstdio>
#include <cstdlib>
typedef int ElementType;
typedef struct HNode *Heap; /* 堆的类型定义 */
struct HNode {
    ElementType *Data; /* 存储元素的数组 */
    int Size;          /* 堆中当前元素个数 */
    int Capacity;      /* 堆的最大容量 */
};
typedef Heap MaxHeap; /* 最大堆 */
typedef Heap MinHeap; /* 最小堆 */

#define MAXDATA 1000  /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */

MaxHeap CreateHeap( int MaxSize )
{ /* 创建容量为MaxSize的空的最大堆 */

    MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
    H->Data = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0] = MAXDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/

    return H;
}

bool IsFull( MaxHeap H )
{
    return (H->Size == H->Capacity);
}

bool Insert( MaxHeap H, ElementType X )
{ /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */
    int i;
 
    if ( IsFull(H) ) { 
        printf("最大堆已满");
        return false;
    }
    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;
}

#define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */

bool IsEmpty( MaxHeap H )
{
    return (H->Size == 0);
}

ElementType DeleteMax( MaxHeap H )
{ /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */
    int Parent, Child;
    ElementType MaxItem, X;

    if ( IsEmpty(H) ) {
        printf("最大堆已为空");
        return ERROR;
    }

    MaxItem = H->Data[1]; /* 取出根结点存放的最大值 */
    /* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
    X = H->Data[H->Size--]; /* 注意当前堆的规模要减小 */
    for( Parent=1; 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  /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;

    return MaxItem;
} 

/*----------- 建造最大堆 -----------*/
void PercDown( 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  /* 下滤X */
            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 );
}

哈夫曼树

什么是哈夫曼树?
实例：将百分制的成绩换成五分制的成绩
算法1:

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-59 60-69 70-79 80-89 90-100
比例 0.05 0.15 0.40 0.30 0.10

查找效率：0.05×1+0.15×2+0.4×3+0.3×4+0.1×4=3.150.05\times1+0.15\times2+0.4\times3+0.3\times4+0.1\times4=3.15

算法2:

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

查找效率：0.05×3+0.15×3+0.4×2+0.3×2+0.1×2=2.20.05\times3+0.15\times3+0.4\times2+0.3\times2+0.1\times2=2.2

启示：根据结点不同的查找效率构造更有效的搜索树

哈夫曼树的定义

带权路径长度(WPL)：设二叉树有n个叶子结点，每个叶子结点带有权值wk，从根结点到每个叶子结点的长度为lk，
则每个叶子结点的带权路径长度之和就是：WPL=∑k=1nwklkWPL=\sum_{k=1}^{n}w_kl_k
最优二叉树或哈夫曼树(Huffman Tree)：WPL最小的二叉树

哈夫曼树的特点

  • 没有度为1的结点
  • n个叶子的哈夫曼树共有2n-1个结点(n个叶子结点，n-1个度为2的结点)
  • 哈夫曼树的任意非叶子结点的左右子树交换后仍然是哈夫曼树
  • 对同一组权值{w1,w2,…,wn}存在同构的多棵哈夫曼树

哈夫曼树的建立

构造哈夫曼树的算法：每次将权值最小的两棵二叉树合并

  • 从结点序列中取出权值最小的和次小的两个节点分别作为树的左子树和右子树
    • 构造存储哈夫曼树节点的最小堆(找到树中最小的结点)
  • 两个节点权值的和作为根节点的权值，将新构造的树插入到哈夫曼树中，并删除原来的两个节点
    • 实现堆删除、插入操作
  • 从剩下n-1(每次删除两个结点，新增一个结点)个二叉树中取出最小的和次小的节点重复上述操作
    • 构造哈夫曼树

哈夫曼树链式存储实现：

typedef struct TreeNode *HuffmanTree;
struct TreeNode
{
    int Weight;
    HuffmanTree Left,Right;
};

哈夫曼编码

实例：给定一个字符串，如何对字符进行编码，可以使得该字符串的编码存储空间最少？

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

分析：

  • 用等长ASCII编码(1字节)：58*8=464位
  • 用等长3位编码：58*3=174位(一共7种字符，使用3位就可以完全表示所有字符了)
  • 不等长编码：出现频率高的字符用的编码短些，出现频率低的字符则编码长一些
  • 进行不等长编码如何避免二义性？
    • 前缀码(prefix code)：任何字符的编码都不是另一字符编码的前缀
      • 如：a(1)，s(101)，t(0)，此时a就是s的前缀，那么二进制字符序列101就有两种不同解释：ata和s
      • 前缀码就消除了这种二义性，可以无二义地解码

使用二叉树进行编码

  • 机器码——>二进制——>二叉树
    • 左右分支：0,1
    • 字符只在叶子结点上，此时一个字符就不会是另一个字符的前缀
      • 如果前面都相同则至少最后一位是不同的，反之如果用子树根结点表示字符，就会存在前缀的情况)
    • 假设有一个字符串aaaxuaxz，四个字符频率为：a:4,u:1,x:2,z:1
      • 一种满足哈夫曼编码要求的编码：00010111010110
      • Cost=1 * 4 + 2 * 2 + 3 *(1+1)=14
    • Cost(字符长度，编码存储空间)的实质：对应二叉树的WPL
      • 存储空间最少——>哈夫曼树

哈夫曼树实现及演示

哈夫曼树建立的关键：找到序列中最小和次小的两个元素——>优先队列——>堆

  • 借助最小堆实现
typedef struct HeapStruct *MinHeap;
typedef struct TreeNode *HuffmanTree;
typedef HuffmanTree ElementType;
struct TreeNode
{
    int Weight;
    HuffmanTree Left,Right;
};
struct HeapStruct
{ 
    ElementType Elements*;   
    int Size,Capacity;        
};

创建用于建立哈夫曼树的最小堆

MinHeap Create(int MaxSize)
{
    MinHeap H=(MinHeap)malloc(sizeof(struct HeapStruct));
    H->Elements*=(ElementType*)malloc((MaxSize+1)sizeof(ElementType));
    H->Size=0,H->Capacity=MaxSize;
    H->Elements[0]->Weight=MinData,H->Elements[0]->Left=H->Elements[0]->Right=NULL;
}

最小堆插入

void InsertMin(MaxHeap H,ElementType T)
{
    if(isFull(H))
    {
        cout<<"最小堆已满"<<endl;
        return;
    }
    for(int i=++H->Size;T->Weight<H->Elements[i/2];i/=2)
        H->Elements[i]=H->Elements[i/2];
    H->Elements[i]=T;
}

最小堆删除

MinHeap DeleteMin(MinHeap H)
{
    int Parent,Child;
    ElementType tmp,minheap;
    if(isEmpty(H))
    {
        cout<<"最小堆已空"<<endl;
        return NULL;
    }
    minheap=H->Elements[0],tmp=H->Elements[H->Size--];
    for(Parent=1;Parent*2<=H->Size;Parent=child)
    {
        Child=Parent*2;
        if(H->Elements[Child]->Weight>H->Elements[Child+1]->Weight)Child++;
        if(T->Weight<=H->Elements[Child]->Weight)break;
        else H->Elements[Parent]=H->Elements[Child];
    }
    H->Elements[Parent]=T;
    return minheap;
}

最小堆建立

BuildMinHeap(MinHeap H)
{
    int Parent,Child;
    ElementType tmp;
    for(int i=H->Size/2;i>=1;i--)
    {
        tmp=H->Elements[i];
        for(Parent=i;Parent*2<=H->Size;Parent=child)
        {
            Child=Parent*2;
            if(H->Elements[Child]->Weight>H->Elements[Child+1]->Weight)Child++;
            if(T->Weight<=H->Elements[Child]->Weight)break;
            else H->Elements[Parent]=H->Elements[Child];
        }
        H->Elements[Parent]=T;
    }
}

建立哈夫曼树

  • 整体时间复杂度：O(NlgN)O(NlgN)
HuffmanTree Huffman(MinHeap H)
//假设H->Size个权值已经存在H->Elements[]->Weight中
{
    HuffmanTree T;
    BuildMinHeap(H);              //将权值调整为最小堆
    while(H->Size>0)              //共进行H->Size-1次的合并
    {
        T=(HuffmanTree)malloc(sizeof(struct TreeNode)); //建立新结点
        T->Left=DeleteMin(H);                           //从堆中删除一个最小结点作为新哈夫曼树结点的左孩子
        T->Right=DeleteMin(H);                          //从堆中删除一个次小结点作为新哈夫曼树结点的右孩子
        T->Weight=T->Left->Weight+T->Right->Weight;     //计算新权值
        InsertMin(H,T->Weight);                         //将新T插入堆
    }
    T=DeleteMin(H);                                     //最后第n次剩的那个结点是哈夫曼树根结点
    return T;
}