数据结构 - 堆(Heap）

数据结构 - 堆(Heap)

1.堆的定义

堆的形式满足完全二叉树的定义：

若 i < ceil(n/2) ，则节点i为分支节点，否则为叶子节点
叶子节点只可能在最大的两层出现，而最大层次上的叶子节点都依次排列在该层最左侧的位置上
如果有度为1的节点，那么只可能有一个，且该节点只有左孩子

根据堆定义的不同，分为大根堆和小根堆：

大根堆每个节点的值都大于其子节点的值
小根堆每个节点的值都小于其子节点的值

除此之外还有一个重要的内容

单节点也符合堆的特质

2.堆的初始化

堆的初始化可以可以分为如下几个步骤（以初始化最大根堆为例）：

首先初始化为完全二叉树形式。
从最后一个具有孩子节点的节点进行调整，如果以该元素为根的子树是最大根堆，则不进行操作，否则将该子树调整为最大根堆（调整思路为不断与子节点进行比较和交换，直至满足最大根堆要求为止）。
数组:[2,7,26,25,19,17,90,3]，初始化为完全二叉树形式。

调整最后一个具有孩子节点的节点[4]，符合最大根堆要求，不进行操作。

调整节点[3]，以满足最大根堆要求，交换[3]和[7]。

调整节点[2]，以满足最大根堆要求，交换[2]和[5]。

调整节点[1]，以满足最大根堆要求，交换[1]和[3]后继续交换[3]和[7]，最终完成初始化，满足最大根堆要求。

3.堆节点的插入和调整

如上图所示，在如上所示图中插入44

堆的初始化和插入的C++语言代码描述

/**

*@Author : Kindear

*@Intro  : DataStrcut C++ Code 以最大根堆为例

**/

#include <bits/stdc++.h>

#define ARR_SIZE 20

using namespace std;

typedef int ElementType;

void AdjustUp(ElementType A[],int k, int len) //该方法用于堆插入调整

{

    int Tmp = A[k]; //暂存k位置的数值

    int i = k/2; //父节点的下标

    while(i > 0 && A[i] < Tmp)

    {

        //如果该节点大于父节点，那么就交换两者的位置，满足最大根堆的要求

        A[k] = A[i];

        k = i;

        i = k/2; //继续向上寻找并调整，直至满足最大根堆要求

    }

    A[k] = Tmp; //

}

void AdjustDown(ElementType A[],int k,int len) //该方法用于堆的初始化

{

    int Tmp = A[k];

    for(int i = 2*k; i <= len; i*=2) //向下筛选

    {

        if(i < len && A[i] < A[i+1]) i++;

        if(Tmp > A[i]) break;

        else

        {

            A[k] = A[i];

            k = i;

        }

    }

    A[k] = Tmp;

}

void BuildMaxHeap(ElementType A[],int len)

{

    for(int i= len/2 ; i > 0; i--)

    {

        AdjustDown(A,i,len);

    }

}

void PrintfElementArray(ElementType A[],int len)

{

    for(int i=1;i<=len;i++)

    {

        printf("%d%c",A[i],i==len?'\n':' ');

    }

}

int main()

{

    ElementType A[] = {0,2,7,26,25,19,17,90,3};

    ElementType B[ARR_SIZE];

    BuildMaxHeap(A,8);

    PrintfElementArray(A,8);

    for(int i=0;i<=8;i++)

    {

        B[i] = A[i];

    }

    B[9] = 44;//插入44

    AdjustUp(B,9,9);

    PrintfElementArray(B,9);

}

参考文档

[1] 数据结构堆可视化:https://visualgo.net/zh/heap

巴特西

数据结构 - 堆(Heap）

数据结构 - 堆(Heap)

参考文档

最新文章

热门文章