5.1 堆

作者: 编程半岛 | 来源:发表于2018-06-19 19:58 被阅读2次

1. 什么是堆

优先队列：一种特殊的“队列”，取出元素的顺序是依照元素的优先权大小，而不是元素进入队列的先后顺序。
优先队列可用完全二叉树表示：

2. 堆的两个特性

结构性：用数组表示的完全二叉树
有序性：任意结点的关键字是其子树所有节点的最大值（最小值）

最大堆（MaxHeap）：也称“大顶堆”：结点为最大值；

最大堆

最小堆（MinHeap）：也称“小顶堆”：结点为最小值.

最小堆
注意：从根结点到任意结点路径上结点序列是有序的

3. 堆的抽象数据类型描述

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

4. 最大堆的操作

最大堆的结构：

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(sizeof( (MaxSize + 1) * ElementsType )); // 数组的第0号元素作为“哨兵”，堆的数据从数组的第1号元素开始存储
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Element[0] = MaxData;  // 定义“哨兵”，MaxData大于堆中所有可能元素的值，便于以后更快操作
    return H;
}

最大堆的插入：
将新增结点插入到从其父结点到根结点的有序序列中。

// 将元素item插入最大堆H，其中H->Elements[0]已定义为哨兵
void Insert(ElementType item, MaxHeap)
{
    int i;
    if ( IsFull(H) )
    {
        printf("最大堆已满");
        return ;
    }
    i = ++H->size;    // 将i指向最大堆的最后一个元素位置
    while(H->Elements[i/2] < item)    // 将插入的item与堆中的序列计较并排序
    {
        H->Elements[i] = H->Elements[i/2];
        i /= 2;
    } 
    H->Elements[i] = item;  // 将item插入
}

最大堆的删除：
取出根结点（最大值）元素，同时删除堆的一个结点。

如图，将根结点58删除后，总共结点数量为4个，因此需要将第五号结点31移至第一号结点的。但是31<44，不满足最大堆的有序性规则，因此需要调序。调序方法：如果该结点小于其孩子，找出孩子中的最大值，然后交换，直到满足最大堆的有序性规则为止。

// 从最大堆中取出键值为最大的元素，并删除一个结点
ElementType DeleteMax(MaxHeap H)
{
    int Parent, Child;
    ElementType MaxItem, temp;
    if ( IsEmpty(H) )
    {
        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->Element[Parent] = temp;
    return MaxItem;
}

最大堆的建立：将已存在的N个元素按照最大堆的要求存放在一个一维数组中。
方法一：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间复杂度为O(NlogN)。
方法二：在线性时间复杂度（O(N)）下建立最大堆。