数据结构之堆的相关知识详解

news/2024/5/19 4:28:56 标签: 数据结构, 算法, 知识图谱, 堆排序, 堆

堆

文章目录

堆的概念及结构

用数组存储表示的完全二叉树

小根堆：树中所有父亲都小于等于孩子，根是最小值

image-20210901114132773

大根堆：树中所有父亲都大于等于孩子，根是最大值

image-20210901114331083

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

堆的实现

堆向下调整算法

我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

image-20210901154040361

上图为向下调整算法调整为小堆的图解

1、从根开始，不断往下调

2、选出左右孩子中较小的，跟父亲比较，如果比父亲小，跟父亲交换，以小的孩子位置继续往下调。如果比父亲大，则停止

代码如下：

void swap(int *p1,int *p2)
{
    int temp=*p1;
    *p1=*p2;
    *p2=temp;
}
void AdjustDown(int *a,int n,int parent)
{
   	int child=parent*2+1; //左孩子，左孩子+1即为右孩子
    while(child<n)
    {
        //选择出左右孩子中较小/大的那个
        //小堆
        if(child+1<n && a[child+1]<a[child])//右孩子存在(防止越界)且如果右孩子比左孩子小
        {
            child++;//那就下标来到右孩子
        }
        
        if(a[child]<a[parent])//小的孩子小于父亲就交换，继续调整
        {
            swap(&a[parent],&a[child]);
            parent=child;
            child=parent*2+1;
        }
        else//小的孩子比父亲大或相等，则不处理，调整结束
        {
            break;
        }
    }
}

堆向上调整算法

void swap(int *p1,int *p2)
{
    int temp=*p1;
    *p1=*p2;
    *p2=temp;
}
void AdjustUp(HPDataType *a,int child)
{
    int parent = (child-1)/2;
    //while(parent>=0) 不对的，parent不会小于0
    while(child > 0)
    {
        if(a[parent]<a[child])
        {
            swap(&a[parent],&a[child]);
            child=parent;
            parent=(child-1)/2;
        }
        else
        {
            break;
        }
    }
}

向上调整算法我们找当前结点的父亲，假如我们调小堆时，如果父亲结点值大于它，则交换，然后进行迭代继续调整，注意我们进行迭代的条件是child>0，如果父亲结点值小于它，则调整结束，此时它已经是小堆

堆的创建

那么如果不满足左右子树是堆，不能直接用向下调整算法，怎么办呢？下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int array[] = {2,5,8,6,4,7};

image-20210901155927395

建堆代码：

void swap(int *p1,int *p2)
{
    int temp=*p1;
    *p1=*p2;
    *p2=temp;
}
void AdjustDown(int *a,int n,int parent)
{
   	int child=parent*2+1; //左孩子，左孩子+1即为右孩子
    while(child<n)
    {
        //选择出左右孩子中较小/大的那个
        //小堆
        if(child+1<n && a[child+1]<a[child])//右孩子存在(防止越界)且如果右孩子比左孩子小
        {
            child++;//那就下标来到右孩子
        }
        
        if(a[child]<a[parent])//小的孩子小于父亲就交换，继续调整
        {
            swap(&a[parent],&a[child]);
            parent=child;
            child=parent*2+1;
        }
        else//小的孩子比父亲大或相等，则不处理，调整结束
        {
            break;
        }
    }
}
int main()
{
    int a[]={2,5,8,6,4,7};
    int n=sizeof(a)/sizeof(a[0]);
    //1、建堆
    int i=0;
    //为了满足向下调整条件，从最后一个非叶子结点开始调整，从下往上调整
    for(i=(n-1-1)/2;i>=0;--i)//最后一个结点的父亲是最后一个非叶子结点
    {
        AdjustDown(a,n,i);//O(N)
    }
}

我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆

void swap(int *p1,int *p2)
{
    int temp=*p1;
    *p1=*p2;
    *p2=temp;
}
void AdjustUp(HPDataType *a,int child)
{
    int parent = (child-1)/2;
    //while(parent>=0) 不对的，parent不会小于0
    while(child > 0)
    {
        if(a[parent]<a[child])
        {
            swap(&a[parent],&a[child]);
            child=parent;
            parent=(child-1)/2;
        }
        else
        {
            break;
        }
    }
}  
int main()
{
    int a[]={2,5,8,6,4,7};
    int n=sizeof(a)/sizeof(a[0]);
	for(int i=0;i<n;i++)
    {
        AdjustUp(a,i);
    } 
    return 0;
}

向上调整算法我们从第一个结点开始调整，直到最后一个结点

建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

每层结点个数*最坏情况向下的调整次数

image-20210901160417065

因此，建堆的时间复杂度为O(N)。

堆的结构

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;

我们给出一个_a指针指向动态开辟的内存，这块内存用来存储数据，_size用来保存当前数据的个数，_capacity用来保存当前的容量

堆的构建

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (hp->_a == NULL)
	{
		perror("malloc");
		return;
	}
	memcpy(hp->_a, a, (sizeof(HPDataType) * n));
	hp->_size = hp->_capacity = n;
	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(hp->_a, n, i);
	}
}

我们构建堆时，可以将初始化的数据以参数形式传进来，利用memcpy函数进行拷贝，将size和capacity进行更新，并进行建堆

堆的销毁

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}

堆的插入

//插入x，保持它继续是堆
void HeapPush(HP* php,HPDataType x)
{
    assert(php);
    //首先看数组空间够不够，不够就要扩容
    if(php->size==php->capacity)
    {
        HPDataType* temp = (HPDataType*)realloc(php->a,php->capacity*2*sizeof(HPDataType));
        if(temp==NULL)
        {
            perror("malloc");
            return;
        }
        php->capacity*=2;
        php->a=temp;
    }
    php->a[size]=x;
  	php->size++;
    AdjustUp(php->a,php->size-1);
}

在进行插入时，我们首先要看数组空间够不够，不够就要扩容，我们每次扩容两倍，扩容完成后，将数组最后元素后面的位置添加新元素，因为我们还要保持继续是堆，故我们将它向上调整一次

image-20210904104217051

堆的删除

//删除堆顶的数据，删除后保持它继续是堆
void HeapPop(HP* php)
{
    assert(php);
    assert(!HeapEmpty(php));
    swap(&php->a[0],&php->a[php->size-1]);
    php->size--;
    AdjustDown(php->a,php->size,0);
}

image-20210904104831194

1.将堆顶元素与堆中最后一个元素进行交换

2.删除堆中最后一个元素

3.将堆顶元素向下调整到满足堆特性为止

取堆顶的数据

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->_a[0];
}

堆的数据个数

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}

堆的判空

// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}

堆的打印

void HeapPrint(Heap* hp)
{
	assert(hp);
	for (int i = 0; i < hp->_size; i++)
	{
		printf("%d ", hp->_a[i]);
	}
	printf("\n");
}

堆的应用

堆排序>堆排序

堆排序>堆排序分两个步骤：

1、建堆

2、排序

那么我们排升序建大堆还是建小堆呢？答案是建大堆。

升序为什么不能建小堆呢？

建堆选出最小的数，花了O(N)的时间复杂度，紧接着如何选次小的数呢？剩下的数父子关系全乱了，向下调整需要满足左右子树都是堆，但是关系都乱了，左右子树可能都不满足向下调整的条件了，故剩下的N-1个数只能重新建堆，效率太低了

升序建大堆

1、选出了最大的数，把最大的数与最后的数交换

2、紧接着选出次大的数，与倒数第二个位置的数交换…

因为堆结构没有破坏，最后一个数不看作堆里面，左右子树依旧是大堆，向下调整即可，选出第二大

建大堆完成后，排序的步骤如图：

image-20210901162302655

排序代码如下：

#include<stdio.h>
void swap(int *p1,int *p2)
{
    int temp=*p1;
    *p1=*p2;
    *p2=temp;
}
//左右子树都是小堆或者大堆
void AdjustDown(int *a,int n,int parent)
{
   	int child=parent*2+1; //左孩子，左孩子+1即为右孩子
    while(child<n)
    {
        //选择出左右孩子中较小/大的那个
        //小堆
        if(child+1<n && a[child+1]>a[child])//右孩子存在(防止越界)且如果右孩子比左孩子小
        {
            child++;//那就下标来到右孩子
        }
        
        if(a[child]>a[parent])//小的孩子小于父亲就交换，继续调整
        {
            swap(&a[parent],&a[child]);
            parent=child;
            child=parent*2+1;
        }
        else//小的孩子比父亲大或相等，则不处理，调整结束
        {
            break;
        }
    }
}
//排序(升序)，排升序要建大堆，排降序要建小堆
void HeapSort(int *a,int n)
{
    //1、建堆
    int i=0;
    //为了满足向下调整条件，从最后一个非叶子结点开始调整，从下往上调整
    for(i=(n-1-1)/2;i>=0;--i)//最后一个结点的父亲是最后一个非叶子结点
    {
        AdjustDown(a,n,i);//O(N)
    }
    //2、排序
    int end=n-1;
    while(end>0)
    {
        swap(&a[0],&a[end]);
        AdjustDown(a,end,0);//O(nlogn)，一次向下调整为层数次 即logn次，while循环一共调整n次，故是nlogn
        end--;
    }
}
int main()
{
    int a[]={2,5,8,6,4,7};
    int n=sizeof(a)/sizeof(a[0]);
    HeapSort(a,n);
    int i =0;
    for(i=0;i<n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

堆排序>堆排序时间复杂度O(N*logN)

欢迎大家学习讨论！


http://www.niftyadmin.cn/n/880317.html

相关文章

数据结构之堆的应用—TopK问题

数据结构之堆的应用—TopK问题

TopK问题 Top-K问题&#xff1a;即求数据结合中前K个最大的元素或者最小的元素&#xff0c;一般情况下数据量都比较大。 这里我们讲解三种方法&#xff1a; 文章目录TopK问题方法一&#xff1a;排序方法二&#xff1a;将N个数建堆&#xff0c;取出前K个方法三&#xff1a;建一个…
阅读更多...
数据结构之二叉树基础OJ练习单值二叉树

数据结构之二叉树基础OJ练习单值二叉树

单值二叉树 题目来源&#xff1a; 单值二叉树 题目描述&#xff1a; 如果二叉树每个节点都具有相同的值&#xff0c;那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时&#xff0c;才返回 true&#xff1b;否则返回 false。 示例 1&#xff1a; 输入&#xff1a;[1,…
阅读更多...
数据结构之二叉树基础OJ练习检查两颗树是否相同

数据结构之二叉树基础OJ练习检查两颗树是否相同

检查两颗树是否相同 题目来源&#xff1a; 检查两颗树是否相同 题目描述&#xff1a; 给你两棵二叉树的根节点 p 和 q &#xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是相同的。 示例 1&…
阅读更多...
数据结构之二叉树基础OJ练习对称二叉树

数据结构之二叉树基础OJ练习对称二叉树

对称二叉树 题目来源&#xff1a;对称二叉树 题目描述&#xff1a; 给定一个二叉树&#xff0c;检查它是否是镜像对称的。 例如&#xff0c;二叉树 [1,2,2,3,4,4,3] 是对称的。 1/ \2 2/ \ / \ 3 4 4 3但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1/ \ 2 2\…
阅读更多...
数据结构之二叉树的基础OJ练习二叉树的遍历

数据结构之二叉树的基础OJ练习二叉树的遍历

二叉树的前序遍历 题目来源&#xff1a;二叉树的前序遍历 题目描述&#xff1a; 给你二叉树的根节点 root &#xff0c;返回它节点值的 前序 遍历。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[1,2,3]示例 2&#xff1a; 输入&#xff1a;root…
阅读更多...
数据结构之二叉树基础OJ练习另一颗树的子树

数据结构之二叉树基础OJ练习另一颗树的子树

另一颗树的子树 题目来源&#xff1a; 另一颗树的子树 题目描述&#xff1a; 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 二叉树 tree 的一棵…
阅读更多...
数据结构之八大排序算法(C语言实现)

数据结构之八大排序算法(C语言实现)

排序 文章目录排序排序的概念及其应用排序的概念排序的定义排序的稳定性排序在现实生活中的应用常见的排序算法常见排序算法的实现直接插入排序希尔排序选择排序堆排序冒泡排序冒泡排序的优化快速排序Hoare法快速排序时间复杂度快速排序的优化挖坑法前后指针法快速排序非递归归…
阅读更多...
硬核两万字文章带你C++入门

硬核两万字文章带你C++入门

C入门 文章目录C入门C关键字命名空间C输入&输出缺省参数缺省参数概念缺省参数分类全缺省参数半缺省参数函数重载函数重载概念名字修饰extern"C"引用引用概念引用特性常引用引用的使用场景传参返回值传值、传引用效率比较函数传参传值和传引用的效率比较值和引用作…
阅读更多...
最新文章

Copyright @ 2022~2023