数据结构——堆(heap)

一.概念

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

二.优先队列完全二叉树表示

堆的两个特性

• 结构性：用数组表示完全二叉树
• 有序性：任一结点的关键字是其子树所有结点的最大值(或最小值) 最大堆(MaxHeap) 最小堆(MinHeap)
• 从根结点到任意结点路径上结点序列的有序性

三.最大堆代码实现（数组实现）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ElementType int

//数组实现完全二叉树表示堆
typedef struct MAXHEAP
{
    ElementType *data;
    int size;
    int Capacity;
} MaxHeap;

MaxHeap *Create(int MaxSize)
{
    MaxHeap *H = (MaxHeap *)malloc(sizeof(MaxHeap));
    H->data = (ElementType *)malloc(sizeof(ElementType) * (MaxSize + 1)); //二叉树我们从下标 1 开始构建 0的位置放置一个哨兵 在最大堆上哨兵的值要大于堆上所有元素 设置哨兵便于后面操作方便
    H->size = 0;
    H->Capacity = MaxSize;
    H->data[0] = INT_MAX; //哨兵的位置要大于堆中所有元素
    return H;
}

bool isFull(MaxHeap *heap)
{
    return heap->size == heap->Capacity;
}

bool isEmpty(MaxHeap *heap)
{
    return heap->size == 0;
}

//将新增结点插入到从其父结点到根结点的有序序列中
//时间复杂度 log(n)
void Insert(MaxHeap *heap, ElementType item)
{
    if (isFull(heap))
    {
        return;
    }
    int i = ++heap->size;
    while (heap->data[i / 2] < item) //利用 heap->data[0]哨兵结束循环 当根结点小于插入元素的情况下 i/2 = 0 此时结束循环 i此时等于1
    {
        heap->data[i] = heap->data[i / 2]; //向下过滤元素 进行比较如果父结点元素小将他向下移动
        i /= 2;
    }
    heap->data[i] = item; //如果父结点等于插入元素 该元素就放在子结点的位置
}

ElementType DeleteMax(MaxHeap *heap)
{
    ElementType Maxitem = heap->data[1];
    ElementType temp = heap->data[heap->size--]; // size对应的就是元素在数组中的下标 这里采取的是将最后一个元素移除 做插入操作来做到删除第一个最大元素 同时满足了堆的有序性
    int parent, child;                           //用最大堆中最后以一个元素从根节点开始向上过滤下层结点
    for (parent = 1; parent * 2 <= heap->size; parent = child)
    {
        child = parent * 2;
        if (child != heap->size && heap->data[child] < heap->data[child + 1])
        {
            child = child + 1; //左右移动使得child指向左右结点较大者
        }
        if (temp >= heap->data[child]) //如果子结点等于插入元素 则将插入元素放在父结点上 原来的temp是这个子结点的子节点 原本是放在后面 现在放在了前面
            break;
        else
            heap->data[parent] = heap->data[child]; //用较大者依次替换父结点
    }
    heap->data[parent] = temp;
    return Maxitem;
}