【数据结构】动图详解二叉树——堆及堆排序

一、树的概念

1、树的特征

树是非线性的数据结构，是递归定义的。

子树之间不能有任何交集

一颗N个节点的树有N-1条边

2、树的相关名词

1、节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6

2、叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I...等节点为叶节点

3、非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G...等节点为分支节点

4、双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点。

5、孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点

6、兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点

7、树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6

8、节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

9、 树的高度或深度：树中节点的最大层次；如上图：树的高度为4（若定义根为第一层，空树为第零层；若定义根节点为第零层，则空树为-1层。）

10、堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

11、节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

12、子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

13、森林：由m（m>0）棵互不相交的树的集合称为森林；

二、树的表示方法

1、左孩子右兄弟表示法

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

该方法思想是让根节点找第一个孩子，让这个孩子去找他的兄弟节点

2、双亲表示法

在数组里存储父亲的下标

三、特殊二叉树

1、在二叉树中，节点个数往往用于衡量时间复杂度

2、对于任何一颗二叉树，度为0的节点总比度为2的节点多1

3、父子节点的关系
$\large leftChild=2*parent+1$

$\large rightChild=2*parent+2$

$\large parent=(child-1)/2$ （左右孩子都是这个公式）

4、满二叉树每一层都是满的，假设该颗满二叉树的高度为h，总节点为N，

则 $\large 2^h-1=N$

$\large h=log(N+1)$

5、完全二叉树前h-1层是满的，最后一层从左往右必须是连续的。

四、堆的向上调整算法建堆及排序

堆是一个完全二叉树

1、向上调整建堆O(N*logN)

建堆特点：越靠近堆顶，节点个数越少，调整次数也少；越接近堆底，节点个数指数级增多，调整次数也多，所以向上调整建堆不如向下调整建堆

void AdjustUp(HPDataType* parr, int child)//向上调整算法,建小堆
{
    int parent = (child - 1) / 2;
    while (parr[parent] > parr[child])//这里大于变小于就是大堆
    {
        Swap(&parr[parent], &parr[child]);
        child = parent;
        parent = (child - 1) / 2;
    }
}

向上调整算法是在数组的末尾插入一个数，把这个数和他的父节点比较，根据建的大堆还是小堆来决定是否交换数据。如果建的是大堆，那么堆顶的那个数字是最大的。建小堆，堆顶是最小的数。

注意：建堆完成后，数组并不是有序的，只是在堆顶选出了数组中最大/最小的数。

这里是在模拟建小堆的过程，如果想用向上调整算法建大堆，在代码注释位置更换比较符号即可

2、向上调整用于排序

我们假设最坏情况下，每一个新的数插入进来都要向上调整，且最多调整次数为（高度-1）次，

那么总调整次数=每一层节点个数*这一层节点最坏向上调整次数

可得T(h)= $\large 2^0*0 + 2^1*1 + 2^2*2$ +·······+ $\large 2^(h-2)*(h-2)+2^(h-1)*(h-1)$

1、化简得T(h)= $\large 2^h*(h-2)+2$

2、已知高度为h，总节点个数为N的完全二叉树， $\large 2^h-1=N$ ——> $\large h=log(N+1)$

在二叉树中，节点个数往往用于衡量时间复杂度

结论：向上调整算法用于建堆的时间复杂度为O(N*logN)，建堆的时间复杂度不如向下调整算法，不采用向上调整来排序。

五、堆的向下调整算法

1、向下调整建堆O(N)

条件：左右子树必须均为大堆/小堆，才能使用向下调整建堆

建堆特点：越靠近堆顶，节点个数越少，调整次数多；越接近堆底，节点个数多，调整次数也少。堆排序使用向下调整。

void AdjustDown(HPDataType* parr, int size, int parent)//向下调整算法,小堆
{
    int minChild = parent * 2 + 1;
    while (minChild<size)
    {
        if (minChild+1<size&&parr[minChild + 1] < parr[minChild])//小堆<，大堆>
        {
            ++minChild;//找出小的下标
        }
        if (parr[minChild] < parr[parent])//小堆<，大堆>
        {
            Swap(&parr[minChild], &parr[parent]);
            parent = minChild;
            minChild = parent * 2 + 1;
        }
        else
            break;
    }
}

向下调整是根据父节点向子节点向下调整，不断向下更新父节点的下标，当左孩子的下标越界时，停止向下调整。

同样，建完堆后，数组并不是有序的，堆顶是最大/最小的数

2、向下调整用于排序

堆排序的原理：1、建堆2、把堆顶元素放到数组末尾3、缩小数组范围微调维持堆形态4、迭代上述步骤至有序。

所以升序建大堆，降序建小堆

//堆排序，实质是选择排序，依次选数，从后往前排，时间复杂度O(N*logN)
//升序大堆
//降序小堆
void HeapSort(int* parr, int size)
{
    for (int i = (size - 1 - 1) / 2; i >= 0; --i)//建堆，时间复杂度O(N)
    {//从最后一个节点的父亲开始调整,不要从size-1开始调整，因为最后一层不用调整
        AdjustDown(parr,size,i);//向下调整算法，这里用于把外部传入的数组进行建堆
    }
    for (int i = 0; i < size; ++i)//将堆顶和最后一个元素互换，再迭代向下调整选出次大/次小
    {
        Swap(&parr[0], & parr[size - 1 - i]);
        AdjustDown(parr, size - 1 - i, 0);//重建堆
    }
}

建堆：从最后一个节点的父亲开始向下调整，直到调整到根。（千万不要从最后一个元素开始建堆，因为叶节点的子树为空，无需向下调整。并且这些叶节点就占了整颗二叉树一半的节点） $\large i=(size-1-1)/2$ 的意思：找到最后一个非叶节点

我们假设最坏情况下，每一个非叶节点都要调整，最多调整次数为（高度-当前层数）次，

那么总调整次数=每一层节点个数*这一层节点最坏向下调整次数

T(h)= $\large 2^0*(h-1)+2^1*(h-2)$ +·······+ $\large 2^(h-3)*2+2^(h-1)*1$ 最后一层无需调整

化简得T(h)= $\large 2^h-h-1$

带入高度与节点数的关系可得时间复杂度为 $\large N-log(N+1)$

即建堆时间复杂度O(N)

重建堆：时间复杂度O(NlogN)，粗略计算方法：最后一层节点个数为 $\large 2^(h-1)$ ，约占总结点的一半，对于最后一层时间复杂度=该层节点数调整次数= $\large 1/2N*logN$ 。其他层节点数量加起来和最后一层一样，但每个节点的调整次数少于最后一层，所以，其它层所有节点加起来的时间复杂度都不如最后一层所有节点的时间复杂度。所以总的重建堆的时间复杂度为O( $\large N*logN$ ）。

3、堆排序总结

1、以升序为例：先找到最后一个非叶节点，采用向下调整算法，再找到倒数第二个非叶节点，重复向下调整算法。

动图如下：

2、将数组调整成大堆后，将堆顶数据（最大的数）和堆底数据进行互换，锁定这个最大的数。这个时候原有的堆形态被破坏，需要重新使用向下调整算法对这个数组重建堆。迭代锁定。

动图如下：

3、向上不如向下是因为第一次建堆效率向下高O(N),原因：

最后一层向下不用考虑

向下算法越往节点多的层，调整次数越少，向上则相反。

4、堆排序初始化堆的时间复杂度为O(N),后续重建堆的时间复杂度为O(NlogN),所以总体复杂度为N+NlogN，即O(N*logN)

六、Top K问题

建大堆还是小堆？

从一串数据中选出前top k大的数字

1、大堆：需要额外相等的一串空间,Pop k次，时间复杂度O(N+k*logN)

2、小堆：开k个空间，取k个数进行堆排序，遍历原数组，遇到比栈顶大的数据就和栈顶数据交换，再向下调整，时间复杂度K+(N-k)*logk,即O(N)

//在文件中创建0-100的随机数
void create(const char* filename)
{
    FILE* pf = fopen(filename, "w");
    for (int i = 0;i < 100;++i)
    {
        fprintf(pf, "%d\n", rand() % 101);
    }
    fclose(pf);
}
void TopK(const char* filename, int k)
{
    FILE* pf = fopen(filename, "r");
    int* smallHeap = (int*)malloc(sizeof(int) * k);
    //把前k个数读到smallHeap中
    for (int i = 0;i < k;++i)
    {
        fscanf(pf, "%d", &smallHeap[i]);
    }
    //建堆
    AdjustDown(smallHeap, k, 0);
    //读取剩余数据
    int val = 0;
    while (fscanf(pf, "%d", &val) != EOF)
    {
        if (val > smallHeap[0])
        {
            smallHeap[0] = val;
            AdjustDown(smallHeap, k, 0);
        }
    }
    for (int i = 0;i < k;++i)
    {
        printf("%d ", smallHeap[i]);
    }
    fclose(pf);
}
int main()
{
    srand((unsigned int)time(NULL));
    const char* filename = "Data.txt";
    int k = 5;
    create(filename);
    TopK(filename, k);
    return 0;
}

现在文件中读取k个数据，文件指针停留在k+1位置处。再继续读入数据即可

从一串数据中选出前top k小的数字

选大堆

七、Heap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int HPDataType;
typedef struct Heap
{
    HPDataType* arr;
    int size;
    int capacity;
}HP;
void HeapInit(HP* php);//初始化
void HeapDestroy(HP* php);//销毁
void HeapPush(HP* php, HPDataType x);//插入x,继续保持堆形态
void HeapPop(HP* php);//删除堆顶元素，继续保持堆形态,用于找次大/次小
HPDataType HeapTop(HP* php);//返回堆顶元素（大堆是最大元素，小堆是最小元素）
bool HeapEmpty(HP* php);//判空
int HeapSize(HP* php);//返回元素个数
void AdjustUp(HPDataType* parr,int child);//向上调整算法
void AdjustDown(HPDataType* parr, int size,int parent);//向下调整算法
void HeapPrint(HP* php);//打印函数，方便观察大小堆

堆的底层是一个顺序表，区别在于堆在插入删除时，需要向上/向下调整算法来保证顺序表中的元素依旧是堆形态。

八、Heap.c

1、堆的初始化和销毁

void HeapInit(HP* php)//初始化
{
    assert(php);
    php->arr = NULL;
    php->size = php->capacity = 0;
}
void HeapDestroy(HP* php)//销毁
{
    assert(php);
    free(php->arr);
    php->size = php->capacity = 0;
}

2、堆的打印

void HeapPrint(HP* php)//打印函数，方便观察大小堆
{
    assert(php);
    for (int i = 0; i < php->size; ++i)
    {
        printf("%d ", php->arr[i]);
    }
    printf("\n");

这个函数是为了方便自己观察顺序表中元素是否是堆，自己加上去的

3、向上调整算法

void AdjustUp(HPDataType* parr, int child)//向上调整算法,建小堆
{
    int parent = (child - 1) / 2;
    while (parr[parent] > parr[child])//这里大于变小于就是大堆
    {
        Swap(&parr[parent], &parr[child]);
        child = parent;
        parent = (child - 1) / 2;
    }
}

数组中每次在尾部插入一个数据，利用 $\large parent=(child-1)/2$ ,把这个数据和他的父节点比较大小，迭代交换。这个数据最坏需要交换（高度-1）次。

在堆中配合HeapPush函数使用。

4、向下调整算法

void AdjustDown(HPDataType* parr, int size, int parent)//向下调整算法,小堆
{
    int minChild = parent * 2 + 1;
    while (minChild < size)
    {
        if (minChild + 1 < size && parr[minChild + 1] < parr[minChild])//小堆<，大堆>
        {
            ++minChild;//找出小的下标
        }
        if (parr[minChild] < parr[parent])//小堆<，大堆>
        {
            Swap(&parr[minChild], &parr[parent]);
            parent = minChild;
            minChild = parent * 2 + 1;
        }
        else
            break;
    }
}

向下调整需要左右子树同时为大堆/小堆。在堆中调整次数为（高度-1）次。通过size控制结束条件。

在堆中配合HeapPop函数使用。

5、堆的插入

void HeapPush(HP* php, HPDataType x)//插入x,继续保持堆形态
{
    assert(php);
    //判断扩容
    if (php->size == php->capacity)
    {
        int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(int));
        if (tmp == NULL)
        {
            perror("realloc fail:\n");
            exit(-1);
        }
        php->capacity = newCapacity;
        php->arr = tmp;
    }
    php->arr[php->size] = x;
    //向上调整算法
    AdjustUp(php->arr, php->size);
    ++php->size;
}

在堆的尾部插入一个数据，这可能会导致堆形态被破坏，通过向上调整算法将这个数字调整到指定位置，让数组重新维持为堆形态。

6、堆的删除

void HeapPop(HP* php)//删除堆顶元素，继续保持堆形态,用于找次大/次小
{
    assert(php);
    assert(!HeapEmpty(php));
    //先把堆顶和最后一个元素交换
    Swap(&php->arr[0], &php->arr[php->size - 1]);
    php->size--;
    //向下调整算法，需要左右子树同为大堆/小堆，小堆换小，大堆换大
    AdjustDown(php->arr, php->size, 0);//向下调整算法
}

堆的删除是把数组首元素进行删除。

1、先将数组首、尾元素进行交换

2、将数组size--，这样就访问不到原堆顶元素

3、对新堆顶元素进行向下调整算法，让数组重新维持堆形态

7、返回堆顶元素、堆的判空、堆的元素个数

HPDataType HeapTop(HP* php)//返回堆顶元素（大堆是最大元素，小堆是最小元素）
{
    assert(php);
    assert(!HeapEmpty(php));
    return php->arr[0];
}
bool HeapEmpty(HP* php)//判空
{
    assert(php);
    return php->size == 0;
}
int HeapSize(HP* php)//返回元素个数
{
    assert(php);
    return php->size;
}

标签：数据结构

本文转载自: https://blog.csdn.net/gfdxx/article/details/126436136
版权归原作者 蒋灵瑜的笔记本 所有，如有侵权，请联系我们删除。