• 堆的实现（C语言）

    目录

    一、树

    1.什么是树？

    2.数的基本概念 

    3.树的表示

    4. 树在实际中的运用（表示文件系统的目录树结构）

     二、二叉树概念及结构

    1.特殊的二叉树：

    2.二叉树的性质

    3.二叉树经典题目

    4.二叉树的存储结构

    三、 堆的概念

    1. 堆的性质

     2. 小堆的实现

    2.1 heap.h

    2.2 test.h 

    2.3 heap.c

    3.注意

    3.1 交换两个数

    3.2 向上调整算法

    3.3 向下调整算法

    3.4 建堆

    3.5 堆排序

    3.6 top-k问题

    一、树

    1.什么是树？

            树(Tree)是n(n≧0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：有且仅有一个特定的称为根的结点。当n>1时，

            其余结点可分为m(m>0)个互不相交的有限集T1、T2、T3……、Tm，其中每个集合本身又是一棵树，并且称为根的子树。

            树的基本概念看下面的图：(1条消息) 树的基本概念_zhuoya_的博客-CSDN博客_树的基本概念

    定义树的时候需要注意的两点：

            n>0时，根的节点是唯一的，不可能存在多个根结点。

            m>0时，子树的个数没有限制，子树一定是不相交的。

    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
    10. 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
    11. 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
    12. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
    13. 森林：由m（m>0）棵互不相交的树的集合称为森林；

     3.树的表示

            树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

    1. typedef int DataType;
    2. struct Node
    3. {
    4. struct Node* _firstChild1; // 第一个孩子结点
    5. struct Node* _pNextBrother; // 指向其下一个兄弟结点
    6. DataType _data; // 结点中的数据域
    7. };

     4. 树在实际中的运用（表示文件系统的目录树结构）

     二、二叉树概念及结构

            1.概念:一棵二叉树是结点的一个有限集合，该集合:1. 或者为空
            2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

     从上图可以看出：
            1. 二叉树不存在度大于2的结点
            2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
            注意：对于任意的二叉树都是由以下几种情况复合而成的：

    1. 特殊的二叉树：

    (1条消息) 数据结构（四）：二叉树_山舟的博客-CSDN博客_二叉树

    （1）满二叉树

            每一层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K（根节点是第1层），且结点总数是(2^k) -1 ，则它就是满二叉树。

    （2）完全二叉树

            完全二叉树是由满二叉树而引出来的。对于深度为K的、有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 满二叉树是一种特殊的完全二叉树。也就是说：完全二叉树的叶子结点只能出现在最下层和次下层，且最下层的叶子结点从左到右连续；前K-1层是满的二叉树。

    （3）非完全二叉树

    2.二叉树的性质

    (1条消息) 【数据结构】之二叉树的5个性质_我叫向同学的博客-CSDN博客_二叉树性质5证明

    二叉树性质1
            性质1：在二叉树的第i层上至多有2^(i-1)个结点（i>=1）。
            如图1-1的二叉树。
            第一层的结点是根结点，只有一个，所以2^(1-1) = 2^0=1。
            第二层有两个结点，所以2^(2-1) = 2^1=2。
            第三层有四个结点，所以2^(3-1) = 2^2=4。
            第四层有八个结点，所以2^(4-1) = 2^3=8。

    图1-1
    通过数据归纳法的论证，可以很容易得出在二叉树的第i层上至多有2^(i-1)（i>=1）个结点的论证。

    二叉树性质2
            性质2：深度为k的二叉树至多有2^k-1个结点（k>=1）。
            这里一点要看清楚，是2^k后再减去1。
            深度为k的意思就是说有k层的二叉树。

    二叉树性质3
            性质3：对于任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
            终端结点数就是叶子结点数，除了叶子结点外，剩下的就是度为1或2的结点数了，我们设n1为度是1的结点数。则树T的结点总数n=n0+n1+n2。
            如下图1-2的例子，结点数为10，他是由A,B,C,D等度为2结点，F,G,H,I,J等度为0的叶子结点和E这个度为1的结点组成。总和为4+1+5=10。

     图1-2

            我们换个角度，数一数它的连接线数，由于根结点只有分出去，没有分支进入，所以分支线总数为结点总数再减去1,。图1-2就是有9个分支。对于A,B,C,D结点来说，他们都有两个分支线出去，而E结点只有一个分支线出去，所以总分支线为4 * 2 + 1*1=9。
            用代数表达就是分支总数=n-1=n1+2n2。因为刚才我们有等式n=n0+n1+n2,所以可以推导出n 0+n1+n2-1=n1+2n2。

     3.二叉树经典题目

    (1条消息) 《数据结构》二叉树的性质及计算题考察_beyond.myself的博客-CSDN博客_二叉树性质的计算

    1. 1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
    2. A. 不存在这样的二叉树
    3.  
    4. B. 200
    5.  
    6. C. 198
    7.  
    8. D. 199
    9.  
    10. 解：设度为0的节点个数为a0，度为2的节点个数为a2，a0=a2+1，199+1=200；选B
    11.  
    12. 2.下列数据结构中，不适合采用顺序存储结构的是（ ）
    13. A. 非完全二叉树
    14.  
    15. B. 堆
    16.  
    17. C. 队列
    18.  
    19. D. 栈
    20.  
    21. 解:只有二叉树不是顺序存储,选A。
    22.  
    23. 3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
    24. A. n
    25.  
    26. B. n+1
    27.  
    28. C. n-1
    29.  
    30. D. n/2
    31.  
    32. 解：
    33.  
    34. 假设度为0节点有a0个
    35.  
    36. 假设度为1节点有a1个
    37.  
    38. 假设度为2节点有a2个
    39.  
    40. 2n = a0+a1+a2
    41.  
    42. 2n = a0+a1+a0-1
    43.  
    44. 2n=2a0-1+a1
    45.  
    46. 因为完全二叉树最后一排的叶节点必须连续，所以度为1的节点只能是1个或者0个，此处如果a1是0，2n=2a0-1,
    47.  
    48. a0=(2n-1)/2,a0不可能是小数，所以a1必须是1，因此2n=2a0,a0=n;选A。
    49.  
    50. 4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
    51. A. 11
    52.  
    53. B. 10
    54.  
    55. C. 8
    56.  
    57. D. 12
    58.  
    59. 解：上一个题那样算虽然能算出叶节点个数a0，但不只是最后一排有叶节点，倒数第二排也有叶节点，所以就算求出来了也没法用，只能用代数法：
    60.  
    61. 过程：①设高度是h(规定根节点层数是1)，已知高度h的二叉树最多有2^h-1个节点，设完全二叉树最后一排比满二叉树少了X个节点，所以有 2^h-1-X=531，即X=2^h-1-531=2^h-532 X最小是1(完全二叉树最后一排最少比满二叉树少1个节点)，X最大是 2^(h-1)-1 (当完全二叉树最后一排只有一个节点时，第 i 行最多有2^(i-1)个节点)
    62.  
    63. ②然后我们不妨带入选项：A:h=11时，X最大是2^10-1=1024-1=1023，带入前面的等式X=2^11-532=2048-532=1516，X最大是1023,1516已经超了，不符合，所以排除A。
    64.  
    65. 同理B:h=11时，X最大是2^9-1=512-1=511，带入前面的等式X=2^10-532=1024-532=492，492
    66.  
    67. C:h=8时，X最大是2^7-1=128-1=127，带入前面的等式X=2^8-532=256-532= -276，X是负数了，不符合，所以排除C。
    68.  
    69. D:h=12时同A，也不符合。 选B。
    70.  
    71. 5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
    72. A. 383
    73.  
    74. B. 384
    75.  
    76. C. 385
    77.  
    78. D. 386
    79.  
    80. 解：
    81.  
    82. 假设度为0节点有a0个
    83.  
    84. 假设度为1节点有a1个
    85.  
    86. 假设度为2节点有a2个
    87.  
    88. 767= a0+a1+a2
    89.  
    90. 767= a0+a1+a0-1
    91.  
    92. 767=2a0-1+a1
    93.  
    94. 只有当a1是0时，a0才不为小数，可直接求出a0=384，选B。
    95.  
    96. 答案：
    97.  
    98. 1.B
    99.  
    100. 2.A
    101.  
    102. 3.A
    103.  
    104. 4.B
    105.  
    106. 5.B

    4.二叉树的存储结构

            二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
            1. 顺序存储
                    顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

             2. 链式存储
                    二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

            普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

    三、 堆的概念

    1. 堆的性质

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

     注意第二题比较三次

    已知小根堆为8,15,10,21,34,16,12，删除关键__牛客网 (nowcoder.com)

    接替思路均与牛客上这题类似

    1. 1.下列关键字序列为堆的是：（）
    2. A 100,60,70,50,32,65
    3. B 60,70,65,50,32,100
    4. C 65,100,70,32,50,60
    5. D 70,65,100,32,50,60
    6. E 32,50,100,70,65,60
    7. F 50,100,70,65,60,32
    8. 2.已知小根堆为8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次
    9. 数是（）。
    10. A 1
    11. B 2
    12. C 3
    13. D 4
    14. 3.一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为
    15. A(11 5 7 2 3 17)
    16. B(11 5 7 2 17 3)
    17. C(17 11 7 2 3 5)
    18. D(17 11 7 5 3 2)
    19. E(17 7 11 3 5 2)
    20. F(17 7 11 3 2 5)
    21. 4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是（）
    22. A[3，2，5，7，4，6，8]
    23. B[2，3，5，7，4，6，8]
    24. C[2，3，4，5，7，8，6]
    25. D[2，3，4，5，6，7，8]
    26. 1.A
    27. 2.C
    28. 3.C
    29. 4.C

     2. 小堆的实现

     下面简单说明一下怎么构建最大堆：

            原始数据为a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}，采用顺序存储方式，对应的完全二叉树如下图所示：

     基本思想：
    首先将每个叶子节点视为一个堆，再将每个叶子节点与其父节点一起构造成一个包含更多节点的对。所以，在构造堆的时候，首先需要找到最后一个节点的父节点，从这个节点开始构造最大堆；直到该节点前面所有分支节点都处理完毕，这样最大堆就构造完毕了。
    假设树的节点个数为n，以1为下标开始编号，直到n结束。对于节点i，其父节点为i/2；左孩子节点为i*2，右孩子节点为i*2+1。最后一个节点的下标为n，其父节点的下标为n/2。
    我们边针对上边数组操作如下图所示，最后一个节点为7，其父节点为16，从16这个节点开始构造最大堆；构造完毕之后，转移到下一个父节点2，直到所有父节点都构造完毕。
    原文链接：https://blog.csdn.net/xiaomucgwlmx/article/details/103522410

        

    2.1 heap.h

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #pragma once
    3.  
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. typedef int HPDataType;
    10. typedef struct Heap//数组实现堆
    11. {
    12. 	HPDataType* a;
    13. 	size_t size;
    14. 	size_t capacity;
    15. }HP;
    16.  
    17. void HeapInit(HP* php);
    18. void HeapDestroy(HP* php);
    19. void Swap(HPDataType* psa, HPDataType* psb);
    20. void AdjustUp(HPDataType* a, size_t child);
    21. void HeapPush(HP* php, HPDataType x);
    22. void HeapPrint(HP* php);
    23. void AdjustDown(HPDataType* a, size_t size, size_t root);
    24. void HeapPop(HP* php);
    25. bool HeapEmpty(HP* php);
    26. size_t HeapSize(HP* php);
    27. HPDataType HeapTop(HP* php);

    2.2 test.h 

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"HEAP.h"
    3. //二叉树
    4. /*父子间下标关系计算公式
    5. leftchild = parent*2 + 1
    6. rightchild = parent*2 + 2
    7. parent = (child - 1)/2
    8. 物理结构是数组，逻辑结构是完全二叉树*/
    9. //实现堆
    10. void TestHeap()
    11. {
    12. 	HP hp;
    13. 	HeapInit(&hp);
    14. 	HeapPush(&hp, 1);
    15. 	HeapPush(&hp, 5);
    16. 	HeapPush(&hp, 3);
    17. 	HeapPush(&hp, 0);
    18. 	HeapPush(&hp, 8);
    19. 	HeapPush(&hp, 9);
    20. 	HeapPop(&hp);
    21. 	HeapPop(&hp);
    22. 	HeapPop(&hp);
    23. 	HeapPop(&hp);
    24. 	HeapPop(&hp);
    25. 	/*HeapPop(&hp);*/
    26. 	/*int ret = HeapEmpty(&hp);
    27. 	printf("%d\n", ret);*/
    28. 	/*size_t count = HeapSize(&hp);
    29. 	printf("%d\n", count);*/
    30. 	/*HPDataType x = HeapTop(&hp);
    31. 	printf("%d\n", x);*/
    32. 	HeapPrint(&hp);
    33. 	HeapDestroy(&hp);
    34. }
    35. //升序 ：时间复杂度：O(N*logN)
    36. //缺陷：空间复杂度O(N)
    37. void HeapSort(int* a, int size)
    38. {
    39. 	HP hp;
    40. 	HeapInit(&hp);
    41. 	for (int i = 0; i < size; i++)
    42. 	{
    43. 		HeapPush(&hp, a[i]);
    44. 	}
    45. 	size_t j = 0;
    46. 	while (!HeapEmpty(&hp))
    47. 	{
    48. 		a[j] = HeapTop(&hp);//对于小堆取到最小数
    49. 		j++;
    50. 		HeapPop(&hp);
    51. 	}
    52. 	HeapDestroy(&hp);
    53. }
    54. int main()
    55. {
    56. 	//TestHeap();
    57. 	int a[] = { 4,3,5,9,6,7,0,2,8,1 };
    58. 	HeapSort(a, sizeof(a) / sizeof(int));
    59. 	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    60. 	{
    61. 		printf("%d ", a[i]);
    62. 	}
    63. 	printf("\n");
    64. 	return 0;
    65. }

     2.3 heap.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"HEAP.h"
    3. void HeapPrint(HP* php)
    4. {
    5. 	assert(php);
    6. 	for (size_t i = 0; i < php->size; i++)
    7. 	{
    8. 		printf("%d ", php->a[i]);
    9. 	}
    10. 	printf("\n");
    11. }
    12. void HeapInit(HP* php)
    13. {
    14. 	assert(php);
    15. 	php->size = 0;
    16. 	php->capacity = 0;
    17. 	php->a = NULL;
    18. }
    19. void HeapDestroy(HP* php)
    20. {
    21. 	assert(php);
    22. 	free(php->a);
    23. 	php->a = NULL;
    24. 	php->size = 0;
    25. 	php->capacity = 0;
    26. }
    27. void Swap(HPDataType* psa, HPDataType* psb)
    28. {
    29. 	HPDataType tmp = *psa;
    30. 	*psa = *psb;
    31. 	*psb = tmp;
    32. }
    33. void AdjustUp(HPDataType* a, size_t child)
    34. {
    35. 	size_t parent = (child - 1) / 2;
    36. 	while (child > 0)//因为child变为0，parent也会变成0，所以只能用child>0判断
    37. 	{
    38. 		if (a[child] < a[parent])
    39. 		{
    40. 			Swap(&a[child], &a[parent]);//交换的是a数组的两个数，改变的是HPDataType,那就要传HPDataType*，改变地址
    41. 			child = parent;
    42. 			parent = (child - 1) / 2;
    43. 		}
    44. 		else
    45. 		{
    46. 			break;
    47. 		}
    48. 	}
    49. }
    50. void HeapPush(HP* php, HPDataType x)//插入x,保证依然是堆
    51. {
    52. 	assert(php);
    53. 	if (php->size == php->capacity)
    54. 	{
    55. 		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    56. 		//先令realloc后等于tmp，判断是否开辟成功，开辟成功再等于php->a
    57. 		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity*sizeof(HPDataType));
    58. 		if (tmp == NULL)
    59. 		{
    60. 			printf("realloc failed\n");
    61. 			exit(-1);
    62. 		}
    63. 		php->a = tmp;
    64. 		php->capacity = newCapacity;
    65. 	}
    66. 	//开辟成功或者容量充足，插入孩子
    67. 	php->a[php->size] = x;
    68. 	++php->size;
    69. 	//向上调整，控制保持是小堆
    70. 	AdjustUp(php->a, php->size - 1);
    71. 	//传新插入的孩子的位置，即将数组的最后的一个元素传过去size-1为最后一个元素的下标，size代表的是数组中有效元素的个数
    72. 	//小堆满足——孩子的元素大小 大于 父亲的元素大小，所以只要不大于就需要进行调整，将孩子向上调整以满足小堆的要求
    73. }
    74. /*void AdjustDown(HPDataType* a, size_t size, size_t root)//从根开始调，即第一个数，用root表示
    75. {
    76. 	size_t rightchild = 0;
    77. 	size_t leftchild = 0;
    78. 	size_t child = 0;
    79. 	while (rightchild < size)
    80. 	{
    81. 		leftchild = root * 2 + 1;
    82. 		rightchild = root * 2 + 2;
    83. 		if (rightchild > size)
    84. 		{
    85. 			break;
    86. 		}
    87. 		child = a[rightchild] < a[rightchild] ? rightchild : leftchild;
    88. 		if (a[child] < a[root])
    89. 		{
    90. 			Swap(&a[child], &a[root]);
    91. 			root = child;
    92. 			rightchild = root * 2 + 2;
    93. 		}
    94. 		else
    95. 		{
    96. 			break;
    97. 		}
    98. 	}
    99. }*/
    100. void AdjustDown(HPDataType* a, size_t size, size_t root)
    101. {
    102. 	size_t parent = root;
    103. 	size_t child = parent * 2 + 1;
    104. 	while (child < size)
    105. 	{
    106. 		if (child + 1 < size && a[child + 1] < a[child])
    107. 		{
    108. 			++child;
    109. 		}
    110. 		if (a[child] < a[parent])
    111. 		{
    112. 			Swap(&a[child], &a[parent]);
    113. 			parent = child;
    114. 			child = parent * 2 + 1;
    115. 		}
    116. 		else
    117. 		{
    118. 			break;
    119. 		}
    120. 	}
    121. }
    122. void HeapPop(HP* php)//删除堆顶的数据（小堆就是删除最小的数据/大堆就是删除最大的数据）
    123. {
    124. 	/*方法一：就是正常的数组的删除，头删，删除后进行数组的挪动，复杂度为O(N),
    125. 	且挪动后父子关系可能混乱而且可能造成不是堆结构了*/
    126. 	/*方法二：把第一个数据与最后一个数据进行交换，然后--size,
    127. 	相当于把最后一个元素删除了，就是相当于进行了数组的头删，而且不需要进行数组的挪动
    128. 	但是交换后不是小堆了，但是有部分子树还是小堆，这个时候进行向下调整即可
    129. 	注意时间复杂度有了优化，交换是O(1),删除也是O(1),向下调整是，设置完全二叉树的高度是h，故最多调整高度次
    130. 	而对于N个结点，2^(h-1) - 1 + 1 <= N <= 2^h - 1,故复杂度可以看做是log(N),相对于方法一更优*/
    131. 	assert(php);
    132. 	assert(php->size > 0);
    133. 	Swap(&php->a[0], &php->a[php->size - 1]);
    134. 	--php->size;
    135. 	AdjustDown(php->a, php->size, 0);
    136. }
    137. bool HeapEmpty(HP* php)
    138. {
    139. 	assert(php);
    140. 	return php->size == 0;
    141. }
    142. size_t HeapSize(HP* php)
    143. {
    144. 	assert(php);
    145. 	return php->size;
    146. }
    147. HPDataType HeapTop(HP* php)
    148. {
    149. 	assert(php);
    150. 	assert(php->size > 0);
    151. 	return php->a[0];
    152. }

    3.注意

    3.1 交换两个数

            对于Swap(&a[child], &a[parent]);，注意交换的是地址才能改变int数组，改变的是int，就要传int*，那就是传地址，那么swap形参用指针接收。

    1. void Swap(HPDataType* psa, HPDataType* psb)
    2. {
    3. 	HPDataType tmp = *psa;
    4. 	*psa = *psb;
    5. 	*psb = tmp;
    6. }

    3.2 向上调整算法

            父子间下标关系计算公式：
                    leftchild = parent*2 + 1
                    rightchild = parent*2 + 2
                    parent = (child - 1)/2
            物理结构是数组，逻辑结构是完全二叉树

    1. void AdjustUp(HPDataType* a, size_t child)
    2. {
    3. 	size_t parent = (child - 1) / 2;
    4. 	while (child > 0)//因为child变为0，parent也会变成0，所以只能用child>0判断
    5. 	{
    6. 		if (a[child] < a[parent])
    7. 		{
    8. 			Swap(&a[child], &a[parent]);//交换的是a数组的两个数，改变的是HPDataType,那就要传HPDataType*，改变地址
    9. 			child = parent;
    10. 			parent = (child - 1) / 2;
    11. 		}
    12. 		else
    13. 		{
    14. 			break;
    15. 		}
    16. 	}
    17. }

    3.3 向下调整算法

    1. void AdjustDown(HPDataType* a, size_t size, size_t root)
    2. {
    3. 	size_t parent = root;
    4. 	size_t child = parent * 2 + 1;//左孩子
    5. 	while (child < size)
    6. 	{
    7. 		//右孩子是左孩子加1，右孩子比size大就越界了
    8. 		if (child + 1 < size && a[child + 1] < a[child])
    9. 		{
    10. 			++child;
    11. 		}
    12. 		if (a[child] < a[parent])
    13. 		{
    14. 			Swap(&a[child], &a[parent]);
    15. 			parent = child;
    16. 			child = parent * 2 + 1;
    17. 		}
    18. 		else
    19. 		{
    20. 			break;
    21. 		}
    22. 	}
    23. }

    3.4 建堆

            向上调整建堆和向下调整建堆的时间复杂度分析：

                    总共有H层，有2^H-1个节点，N个节点，即N = 2^H-1

                    向上调整累计建堆次数：2^1*1+2^2*2+2^3*3+......+2^(H-1)*(H-1)

                    向下调整累计建堆次数：2^0*(h-1)+2^1*(h-2)+......+2^(h-2)*1

                    最坏情况总的调整次数 = 每层的数据个数*向下调整的次数

                    经计算时间复杂度为向下调整为O(N)，而向上调整建堆为O(N)*logN

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. void Swap(int* x, int* y)
    4. {
    5. 	int temp = *x;
    6. 	*x = *y;
    7. 	*y = temp;
    8. }
    9. void AdjustUp(int* a, size_t child)
    10. {
    11. 	/*父子间下标关系计算公式
    12. 	leftchild = parent*2 + 1
    13. 	rightchild = parent*2 + 2
    14. 	parent = (child - 1)/2
    15. 	物理结构是数组，逻辑结构是完全二叉树*/
    16. 	//向上调整算法，
    17. 	size_t parent = (child - 1) / 2;
    18. 	while (child > 0)//因为child变为0，parent也会变成0，所以只能用child>0判断
    19. 	{
    20. 		if (a[child] < a[parent])
    21. 		{
    22. 			Swap(&a[child], &a[parent]);
    23. 			//交换的是a数组的两个数，改变的是int,那就要传int*，改变地址
    24. 			child = parent;
    25. 			parent = (child - 1) / 2;
    26. 		}
    27. 		else
    28. 		{
    29. 			break;
    30. 		}
    31. 	}
    32. }
    33. void HeapSort(int* a, int n)
    34. {
    35. //向上调整--建堆
    36. 	int i = 0;
    37. 	for (i = 1; i < n; i++)
    38. 	{
    39. 		AdjustUp(a, i);
    40. 	}
    41. //向下调整--建堆
    42.     /*for (i = (n - 1 - 1) / 2; i >= 0; i--)//最后一个节点的父亲开始调整
    43. 	{
    44. 		AdjustDown(a, n, i);
    45. 	}*/
    46.   
    47. }
    48. int main()
    49. {
    50. 	int a[10] = { 5,7,8,9,20,50,10,30,6,11 };
    51. 	HeapSort(a, 10);
    52. 	int j = 0;
    53. 	for (j = 0; j < 10; j++)
    54. 	{
    55. 		printf("%d ", a[j]);
    56. 	}
    57. 	return 0;
    58. }

    3.5 堆排序

    1. void HeapSort(int* a, int n)
    2. {
    3. 	int i = 0;
    4. 	/*for (i = 1; i < n; i++)
    5. 	{
    6. 		AdjustUp(a, i);
    7. 	}*/
    8. 	for (i = (n - 1 - 1) / 2; i >= 0; i--)//最后一个节点的父亲开始调整
    9. 	{
    10. 		AdjustDown(a, n, i);
    11. 	}
    12. 	size_t end = n - 1;
    13. 	while (end > 0)
    14. 	{
    15. 		Swap(&a[0], &a[end]);
    16. 		AdjustDown(a, end, 0);
    17. 		--end;
    18. 	}
    19. }

    小堆--升序

    大堆--降序

    3.6 top-k问题

            TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
            对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
    1. 用数据集合中前K个元素来建堆
            前k个最大的元素，则建小堆；
            前k个最小的元素，则建大堆。
    2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
            将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. void Swap(int* x, int* y)
    8. {
    9. 	int temp = *x;
    10. 	*x = *y;
    11. 	*y = temp;
    12. }
    13. void AdjustDown(int* a, size_t size, size_t root)
    14. {
    15. 	size_t parent = root;
    16. 	size_t child = parent * 2 + 1;
    17. 	while (child < size)
    18. 	{
    19. 		if (child + 1 < size && a[child + 1] < a[child])
    20. 		{
    21. 			++child;
    22. 		}
    23. 		if (a[child] < a[parent])
    24. 		{
    25. 			Swap(&a[child], &a[parent]);
    26. 			parent = child;
    27. 			child = parent * 2 + 1;
    28. 		}
    29. 		else
    30. 		{
    31. 			break;
    32. 		}
    33. 	}
    34. }
    35. void PrintTopK(int* a, int n, int k)
    36. {
    37. 	// 1. 建堆--用a中前k个元素建堆
    38. 	int* kminHeap = (int*)malloc(sizeof(int) * k);
    39. 	assert(kminHeap);
    40.  
    41. 	for (int i = 0; i < k; i++)
    42. 	{
    43. 		kminHeap[i] = a[i];
    44. 	}
    45. 	for (int j = (k - 1 - 1) / 2; j >= 0; j--)
    46. 	{
    47. 		AdjustDown(kminHeap, k, j);
    48. 	}
    49. 	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
    50. 	for (int i = k; i < n; i++)
    51. 	{
    52. 		if (a[i] > kminHeap[0])
    53. 		{
    54. 			kminHeap[0] = a[i];
    55. 			AdjustDown(kminHeap, k, 0);
    56. 		}
    57. 	}
    58. 	for (int j = 0; j < k; j++)
    59. 	{
    60. 		printf("%d ",kminHeap[j]);
    61. 	}
    62.  
    63. }
    64. void TestTopk()
    65. {
    66. 	int n = 10000;
    67. 	int* a = (int*)malloc(sizeof(int) * n);
    68. 	srand(time(0));
    69. 	for (size_t i = 0; i < n; ++i)
    70. 	{
    71. 		a[i] = rand() % 1000000;
    72. 	}
    73. 	a[5] = 1000000 + 1;
    74. 	a[1231] = 1000000 + 2;
    75. 	a[531] = 1000000 + 3;
    76. 	a[5121] = 1000000 + 4;
    77. 	a[115] = 1000000 + 5;
    78. 	a[2335] = 1000000 + 6;
    79. 	a[9999] = 1000000 + 7;
    80. 	a[76] = 1000000 + 8;
    81. 	a[423] = 1000000 + 9;
    82. 	a[3144] = 1000000 + 10;
    83. 	PrintTopK(a, n, 10);
    84. }
    85. int main()
    86. {
    87. 	TestTopk();
    88. 	return 0;
    89. }

  • 相关阅读:
    MongoDB权限控制
    Streamlit 数据科学必备工具
    区块链Layer 1与Layer 2扩展解决方案
    Elasticsearch 对于大数据量（上亿量级）的聚合如何实现？
    点赋科技：如何提高淘宝店铺的流量？
    【C++基础】观察者模式（“发布-订阅”模式）
    python JPG图片手动圈画掩膜Mask轮廓ROI
    用golang开发系统软件的一些细节
    C# Onnx 轻量实时的M-LSD直线检测
    ES6面试题
  • 原文地址：https://blog.csdn.net/weixin_57604904/article/details/127803236