title: 【Heap】
date: 2023-09-28 20:15:27
tags: 数据结构

堆

定义

==采用**数组存储的完全二叉树**==

注意：data[0]用来存放==哨兵==

分类

最小堆（MinHeap）：任一结点的data小于其所有子树结点的data

最大堆（MinHeap）：任一结点的data大于其所有子树结点的dat

操作（以MaxHeap为例）

对象集

typedef struct HeapNode 
{
	ElementType data[Maxsize];
    int size;
}* MaxHeap;

下滤筛选

void HeapAdjust(MaxHeap H,int s)
{
    ElementType t = H->data[s];
    for( int i=2*s; i<=n; i*=2)
    {
        if(i < H->size && H->data[i] < H->data[i+1])	//i < H->size说明H->data[i+1]存在
            i++;
        if(t >= H->data[i])		break;
        else	{	H->data[s]=H->data[i];	s=i;	}
    }
    H->data[s]=t;
}

下滤：用于删除堆顶元素后，调整堆

上滤筛选

void HeapAdjust(MaxHeap H,int s)
{
    ElementType t = H->data[s];
    for( int i=s/2; i>=1; i/=2)
    {
        if(H->data[i] >= t)		break;
        else	{	H->data[s]=H->data[i];		s=i;	}
    }
    H->data[s]=t;
}

上滤：用于向堆中插入一个元素

最大堆的初始化创建

MaxHeap CreatHeap(int Max)
{
    MaxHeap H=(MaxHeap)malloc(sizeof((struct HeapNode)));
    H->data[0]=MaxData;	//INT_MAX
    H->size=0;
    return H;
}

最大堆的插入

void Insert(MaxHeap H,ElementType t)
{
    int i;
    if(H->size>=Maxsize)
        return;
    for(i=++H->size;t>H->data[i/2];i/=2)
        H->data[i]=H->data[i/2];
    H->data[i]=t;
}

注：H->data[0]是哨兵，它不会小于堆中的最大元素，其作用：控制循环结束。

最大堆的删除

步骤

删除并且返回根节点（最大值）

代码

ElementType Delete(MaxHeap H)
{
    if(H->size==0)
        return NULL;
    ElementType max=H->data[1];	//取出根节点最大值，最后return
    
   /* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */ 
    ElementType t=H->data[H->size--];
    int parent,child;
    for(parent=1;parent*2<=H->size;parent=child)	//若parent*2>H->size说明parent没有左儿子，也就更没有右儿子
    {
        child=parent*2;		//child指向左右儿子最大的那个，先初始赋值左儿子
        if((child!=H->size)&&H->data[child] < H->data[child+1])	//child!=H->size说明有右儿子
            child++;	
        if(t>=H->data[child])	break;
        else
            H->data[parent]=H->data[child];
    }
    H->data[parent]=t;
    return max;
}

• 第10行parent*=2错误，必须是parent=child,作用是parent索引变成儿子索引，向下交换
• 第8行~~data[H->size]~~错误，必须是data[H->size--]

最大堆的建立

法一：

步骤：

（1）调用Insert函数，将N个元素一个个相继插入到一个初始为空的堆Heap中去。

（2）其时间复杂度为O(N logN)。

MaxHeap BuildHeap ()
{
    MaxHeap H=(MaxHeap)malloc(sizeof((struct HeapNode)));
    H->data[0]=MaxData;		//INT_MAX
    H->size=0;
    ElementType t;
    for(int i=0;i<n;i++)
    {
        cin>>t;
        Insert(H,t);
    }
    return H;
}

法二：

步骤：

（1）将N个元素按输入顺序存入，先满足完全二叉树的结构特性

（2）调整各结点位置，以满足最大堆的有序特性。

代码

MaxHeap BuildHeap ()
{
    MaxHeap H=(MaxHeap)malloc(sizeof((struct HeapNode)));
    H->data[0]=MaxData;		//INT_MAX
    H->size=0;
    
    ElementType t;
    for(int i=1;i<=n;i++)
    {
        cin>>H->data[i];
        if
            
    }
    return H;
}