Day14 堆及其相关操作

堆的两个特性：

结构性：用数组表示的完全二叉树

有序性：任一结点的关键字是其子树所有结点的最大值（或最小值），即为大顶堆（小顶堆）

#include<cstdio>
#include<iostream>
#include<malloc.h>

using namespace std;

typedef struct HeapStruct *MaxHeap;
struct HeapStruct{
    int *Elements;
    int Size;
    int Capacity;
};

MaxHeap Create(int MaxSize,int MaxData)
{
    MaxHeap H=(struct HeapStruct*)malloc(sizeof(struct HeapStruct));
    H->Elements=(int *)malloc((MaxSize+1)*sizeof(int));
    H->Size=0;
    H->Capacity=MaxSize;
    H->Elements[0]=MaxData;//哨兵
    return H;
}
int IsFull(MaxHeap H)
{
    if(H->Size==H->Capacity)
        return 1;
    else return 0;
}
int IsEmpty(MaxHeap H)
{
    if(H->Size==0)
        return 1;
    else return 0;
}
void Insert(MaxHeap H,int item)
{//将元素item插入最大堆H，其中H->Element[0]已经定义为哨兵
    int i;
    if(IsFull(H))
    {
        printf("FULL");
        return;
    }
    i=++H->Size;//i指向插入后堆中的最后一个元素的位置
    for(;H->Elements[i/2]<item;i/=2)
    {
        H->Elements[i]=H->Elements[i/2];//向下过滤结点
    }
    H->Elements[i]=item;
}

int DeleteMax(MaxHeap H)
{//从最大堆H中取出键值为最大的元素，并且删除一个结点
    int Parent,Child;
    int MaxItem,temp;
    if(IsEmpty(H))
    {
        printf("Empty");
        return -1;
    }
    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++;//Child指向左右子结点中较大者
        if(temp>=H->Elements[Child])break;
        else//移动temp元素到下一层
            H->Elements[Parent]=H->Elements[Child];
    }
    H->Elements[Parent]=temp;
    return MaxItem;
}


int main()
{
    MaxHeap s;
    s=Create(100,10000);
    Insert(s,2);
    Insert(s,9);
    Insert(s,6);
    Insert(s,7);
    Insert(s,3);
    int m;
    m=DeleteMax(s);
    printf("%d\n",m);
}

ps:小顶堆

#include<cstdio>
#include<iostream>
#include<malloc.h>

using namespace std;

typedef struct HeapStruct *MinHeap;
struct HeapStruct{
    int *Elements;
    int Size;
    int Capacity;
};

MinHeap Create(int MaxSize,int MinData)
{
    MinHeap H=(struct HeapStruct*)malloc(sizeof(struct HeapStruct));
    H->Elements=(int *)malloc((MaxSize+1)*sizeof(int));
    H->Size=0;
    H->Capacity=MaxSize;
    H->Elements[0]=MinData;//哨兵
    return H;
}
int IsFull(MinHeap H)
{
    if(H->Size==H->Capacity)
        return 1;
    else return 0;
}
int IsEmpty(MinHeap H)
{
    if(H->Size==0)
        return 1;
    else return 0;
}
void Insert(MinHeap H,int item)
{//将元素item插入最小堆H，其中H->Element[0]已经定义为哨兵
    int i;
    if(IsFull(H))
    {
        printf("FULL");
        return;
    }
    i=++H->Size;//i指向插入后堆中的最后一个元素的位置
    for(;H->Elements[i/2]>item;i/=2)
    {
        H->Elements[i]=H->Elements[i/2];//向下过滤结点
    }
    H->Elements[i]=item;
}

int DeleteMin(MinHeap H)
{//从最小堆H中取出键值为最小的元素，并且删除一个结点
    int Parent,Child;
    int MinItem,temp;
    if(IsEmpty(H))
    {
        printf("Empty");
        return -1;
    }
    MinItem=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++;//Child指向左右子结点中较小者
        if(temp<=H->Elements[Child])break;
        else//移动temp元素到下一层
            H->Elements[Parent]=H->Elements[Child];
    }
    H->Elements[Parent]=temp;
    return MinItem;
}


int main()
{
    MinHeap s;
    s=Create(100,-1);
    Insert(s,2);
    Insert(s,9);
    Insert(s,6);
    Insert(s,7);
    Insert(s,3);
    int m,m1,m2,m3,m4;
    m=DeleteMin(s);
    m1=DeleteMin(s);
    m2=DeleteMin(s);
    m3=DeleteMin(s);
    m4=DeleteMin(s);
    printf("%d %d %d %d %d\n",m,m1,m2,m3,m4);
}