《数据结构基础知识》堆（Heap）及堆的操作

什么是堆（Heap）

• 堆一定是完全二叉树
• 堆的每一个节点一定不大于或不小于左右孩子

根节点最大的是大根堆，根节点最小的是小根堆

堆的操作

操作集抽象表达（以大根堆为例）

• MaxHeap Create(int MaxSize)：创造一个空的大根堆
• Boolean IsFull(MaxHeap H)：判断大根堆H是否为满
• Int Insert(MaxHeap H,ElementType item)：将元素item插入大根堆H
• Boolean IsEmpty(MaxHeap H)：判断大根堆H是否为空
• ElementType DeleteMax(MaxHeap H)：删除并返回堆中最大值（根节点）

具体实现

大根堆的结构

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((MaxSize+1)*sizeof(ElementType));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Elements[0] = MaxData;  //哨兵，大根堆存入最大值，小根堆最小值
    return H;
}

插入堆元素

• 判断堆是否已满
• 把新元素插入堆底最后一个元素后面
• 与父节点比较，大于就上移，小于说明符合大根堆

int Insert(MaxHeap H,ElementType item)
{
    int i;
    if(IsFull(H)){
        printf("堆已满");
        return 0;
    }
    i=H->Size++;  //i指向对最后一个元素位置，同时堆元素个数+1
    for(;H->Elements[i/2]<item;i/=2){ //由于哨兵存在不需要判断i
        H->Elements[i]=H->Elements[i/2]; //插入元素上移
    }
    H->Elements[i]=item;
    return 1；
}

删除堆元素（出堆）

• 将堆顶元素取出，将堆底最后一个元素移到堆顶
• 如果有左右孩子，左右孩子比较大小
• 左右孩子最大的与父元素比较，大于说明符合大根堆
• 小于则与左右孩子最大值交换，并继续与左右孩子比较，
• 直到符合大根堆或者叶节点

ElementType DeleteMax(MaxHeap H)
{
    int parent,child;
    ElementType MaxItem,temp;
    if(IsEmpty(H)){
        printf("堆已空");
        return 0;
    }
    MaxItem = H->Elements[1];//取堆元素最大值
    temp = H->Elements[H->Size--];//取堆最后一个元素作为堆顶元素，堆元素个数-1
    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指向左右孩子最大值
        if(H->Elements[child]<=temp){
            break; //堆顶当前元素就是最大的
        }else{
            H->Elements[parent] = H->Elements[child];  //堆顶元素下移
        }
    }
    H->Elements[parent]=temp;
    return MaxItem;
}

杂记

建堆的初始排序有两种

• 边插入边排序，时间复杂度为O(nlogn)
• 先全部插入，再进行排序，时间复杂度为O(n)

注意：两者实现后初始堆可能出现不同，表现为堆底元素可能左右互换