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

转x33g5p2x  于2021-10-07 转载在 其他  
字(5.3k)|赞(0)|评价(0)|浏览(576)

堆的概念及结构

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

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

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

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

堆的实现

堆向下调整算法

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

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

上图为向下调整算法调整为小堆的图解
1、从根开始，不断往下调

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

代码如下：

  1. void swap(int *p1,int *p2)
  2. {
  3.     int temp=*p1;
  4.     *p1=*p2;
  5.     *p2=temp;
  6. }
  7. void AdjustDown(int *a,int n,int parent)
  8. {
  9.    	int child=parent*2+1; //左孩子，左孩子+1即为右孩子
  10.     while(child<n)
  11.     {
  12.         //选择出左右孩子中较小/大的那个
  13.         //小堆
  14.         if(child+1<n && a[child+1]<a[child])//右孩子存在(防止越界)且如果右孩子比左孩子小
  15.         {
  16.             child++;//那就下标来到右孩子
  17.         }
  18.         
  19.         if(a[child]<a[parent])//小的孩子小于父亲就交换，继续调整
  20.         {
  21.             swap(&a[parent],&a[child]);
  22.             parent=child;
  23.             child=parent*2+1;
  24.         }
  25.         else//小的孩子比父亲大或相等，则不处理，调整结束
  26.         {
  27.             break;
  28.         }
  29.     }
  30. }

堆向上调整算法

  1. void swap(int *p1,int *p2)
  2. {
  3.     int temp=*p1;
  4.     *p1=*p2;
  5.     *p2=temp;
  6. }
  7. void AdjustUp(HPDataType *a,int child)
  8. {
  9.     int parent = (child-1)/2;
  10.     //while(parent>=0) 不对的，parent不会小于0
  11.     while(child > 0)
  12.     {
  13.         if(a[parent]<a[child])
  14.         {
  15.             swap(&a[parent],&a[child]);
  16.             child=parent;
  17.             parent=(child-1)/2;
  18.         }
  19.         else
  20.         {
  21.             break;
  22.         }
  23.     }
  24. }

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

堆的创建

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

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

建堆代码：

  • 向下调整算法建堆：
  1. void swap(int *p1,int *p2)
  2. {
  3.     int temp=*p1;
  4.     *p1=*p2;
  5.     *p2=temp;
  6. }
  7. void AdjustDown(int *a,int n,int parent)
  8. {
  9.    	int child=parent*2+1; //左孩子，左孩子+1即为右孩子
  10.     while(child<n)
  11.     {
  12.         //选择出左右孩子中较小/大的那个
  13.         //小堆
  14.         if(child+1<n && a[child+1]<a[child])//右孩子存在(防止越界)且如果右孩子比左孩子小
  15.         {
  16.             child++;//那就下标来到右孩子
  17.         }
  18.         
  19.         if(a[child]<a[parent])//小的孩子小于父亲就交换，继续调整
  20.         {
  21.             swap(&a[parent],&a[child]);
  22.             parent=child;
  23.             child=parent*2+1;
  24.         }
  25.         else//小的孩子比父亲大或相等，则不处理，调整结束
  26.         {
  27.             break;
  28.         }
  29.     }
  30. }
  31. int main()
  32. {
  33.     int a[]={2,5,8,6,4,7};
  34.     int n=sizeof(a)/sizeof(a[0]);
  35.     //1、建堆
  36.     int i=0;
  37.     //为了满足向下调整条件，从最后一个非叶子结点开始调整，从下往上调整
  38.     for(i=(n-1-1)/2;i>=0;--i)//最后一个结点的父亲是最后一个非叶子结点
  39.     {
  40.         AdjustDown(a,n,i);//O(N)
  41.     }
  42. }

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

  • 向上调整算法建堆
  1. void swap(int *p1,int *p2)
  2. {
  3.     int temp=*p1;
  4.     *p1=*p2;
  5.     *p2=temp;
  6. }
  7. void AdjustUp(HPDataType *a,int child)
  8. {
  9.     int parent = (child-1)/2;
  10.     //while(parent>=0) 不对的，parent不会小于0
  11.     while(child > 0)
  12.     {
  13.         if(a[parent]<a[child])
  14.         {
  15.             swap(&a[parent],&a[child]);
  16.             child=parent;
  17.             parent=(child-1)/2;
  18.         }
  19.         else
  20.         {
  21.             break;
  22.         }
  23.     }
  24. }  
  25. int main()
  26. {
  27.     int a[]={2,5,8,6,4,7};
  28.     int n=sizeof(a)/sizeof(a[0]);
  29. 	for(int i=0;i<n;i++)
  30.     {
  31.         AdjustUp(a,i);
  32.     } 
  33.     return 0;
  34. }

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

建堆的时间复杂度

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

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

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

堆的结构

  1. typedef int HPDataType;
  2. typedef struct Heap
  3. {
  4. 	HPDataType* _a;
  5. 	int _size;
  6. 	int _capacity;
  7. }Heap;

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

堆的构建

  1. // 堆的构建
  2. void HeapCreate(Heap* hp, HPDataType* a, int n)
  3. {
  4. 	assert(hp);
  5. 	hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
  6. 	if (hp->_a == NULL)
  7. 	{
  8. 		perror("malloc");
  9. 		return;
  10. 	}
  11. 	memcpy(hp->_a, a, (sizeof(HPDataType) * n));
  12. 	hp->_size = hp->_capacity = n;
  13. 	//建堆
  14. 	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  15. 	{
  16. 		AdjustDown(hp->_a, n, i);
  17. 	}
  18. }

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

堆的销毁

  1. // 堆的销毁
  2. void HeapDestory(Heap* hp)
  3. {
  4. 	assert(hp);
  5. 	free(hp->_a);
  6. 	hp->_a = NULL;
  7. 	hp->_capacity = hp->_size = 0;
  8. }

堆的插入

  1. //插入x，保持它继续是堆
  2. void HeapPush(HP* php,HPDataType x)
  3. {
  4.     assert(php);
  5.     //首先看数组空间够不够，不够就要扩容
  6.     if(php->size==php->capacity)
  7.     {
  8.         HPDataType* temp = (HPDataType*)realloc(php->a,php->capacity*2*sizeof(HPDataType));
  9.         if(temp==NULL)
  10.         {
  11.             perror("malloc");
  12.             return;
  13.         }
  14.         php->capacity*=2;
  15.         php->a=temp;
  16.     }
  17.     php->a[size]=x;
  18.   	php->size++;
  19.     AdjustUp(php->a,php->size-1);
  20. }

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

堆的删除

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

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

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

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

取堆顶的数据

  1. // 取堆顶的数据
  2. HPDataType HeapTop(Heap* hp)
  3. {
  4. 	assert(hp);
  5. 	return hp->_a[0];
  6. }

堆的数据个数

  1. // 堆的数据个数
  2. int HeapSize(Heap* hp)
  3. {
  4. 	assert(hp);
  5. 	return hp->_size;
  6. }

堆的判空

  1. // 堆的判空
  2. int HeapEmpty(Heap* hp)
  3. {
  4. 	assert(hp);
  5. 	return hp->_size == 0;
  6. }

堆的打印

  1. void HeapPrint(Heap* hp)
  2. {
  3. 	assert(hp);
  4. 	for (int i = 0; i < hp->_size; i++)
  5. 	{
  6. 		printf("%d ", hp->_a[i]);
  7. 	}
  8. 	printf("\n");
  9. }

堆的应用

堆排序

堆排序分两个步骤：

1、建堆

2、排序

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

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

升序建大堆

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

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

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

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

排序代码如下：

  1. #include<stdio.h>
  2. void swap(int *p1,int *p2)
  3. {
  4.     int temp=*p1;
  5.     *p1=*p2;
  6.     *p2=temp;
  7. }
  8. //左右子树都是小堆或者大堆
  9. void AdjustDown(int *a,int n,int parent)
  10. {
  11.    	int child=parent*2+1; //左孩子，左孩子+1即为右孩子
  12.     while(child<n)
  13.     {
  14.         //选择出左右孩子中较小/大的那个
  15.         //小堆
  16.         if(child+1<n && a[child+1]>a[child])//右孩子存在(防止越界)且如果右孩子比左孩子小
  17.         {
  18.             child++;//那就下标来到右孩子
  19.         }
  20.         
  21.         if(a[child]>a[parent])//小的孩子小于父亲就交换，继续调整
  22.         {
  23.             swap(&a[parent],&a[child]);
  24.             parent=child;
  25.             child=parent*2+1;
  26.         }
  27.         else//小的孩子比父亲大或相等，则不处理，调整结束
  28.         {
  29.             break;
  30.         }
  31.     }
  32. }
  33. //排序(升序)，排升序要建大堆，排降序要建小堆
  34. void HeapSort(int *a,int n)
  35. {
  36.     //1、建堆
  37.     int i=0;
  38.     //为了满足向下调整条件，从最后一个非叶子结点开始调整，从下往上调整
  39.     for(i=(n-1-1)/2;i>=0;--i)//最后一个结点的父亲是最后一个非叶子结点
  40.     {
  41.         AdjustDown(a,n,i);//O(N)
  42.     }
  43.     //2、排序
  44.     int end=n-1;
  45.     while(end>0)
  46.     {
  47.         swap(&a[0],&a[end]);
  48.         AdjustDown(a,end,0);//O(nlogn)，一次向下调整为层数次 即logn次，while循环一共调整n次，故是nlogn
  49.         end--;
  50.     }
  51. }
  52. int main()
  53. {
  54.     int a[]={2,5,8,6,4,7};
  55.     int n=sizeof(a)/sizeof(a[0]);
  56.     HeapSort(a,n);
  57.     int i =0;
  58.     for(i=0;i<n;i++)
  59.     {
  60.         printf("%d ",a[i]);
  61.     }
  62.     return 0;
  63. }

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

欢迎大家学习讨论！

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/attemptendeavor/article/details/120096950

内容来源于网络，如有侵权，请联系作者删除！

数据结构算法堆排序知识图谱堆

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com