• 堆-----数据结构


    引言

    什么是堆?堆是一种特殊的数据结构(用数组表示的树)。

    为什么要使用到堆?比如一场比赛,如果使用擂台赛的方式来决出冠军(实力第一),就很难知道实力第二的队伍是什么了。

    但是下图能很清楚的表示各队伍的强弱关系。

    堆的特点

    上图就是一个最大堆,解释:每一个圆都是一个节点,数字代表着键值,其中95是93和92的父节点,93和92是95的子节点,93和92是兄弟节点(父节点为同一个),根节点就是键值最大的节点,为95,最后一个节点是87,最后一个左子节点也是87。

    最大堆的特点

    满足以下三点

    1.每个节点最多可以有两个子节点。

    2.根节点的键值是所有堆节点键值中最大者,且每个节点的值都大于其子(孩子)节点。

    3.除了根节点没有兄弟节点,最后一个左子节点可以没有兄弟节点,其他节点必须有兄弟节点。

    最好是自己理解,不用强记 。其中有一点要注意:A的兄弟节点的子节点可能大于A,相当于在比赛中,其中一个小组都是弱队,那么一个弱队却可以闯入半决赛一样。

    最小堆的特点的话就将第二点中的大改为小就可以了,其他的特点一样。这里讨论的是最大堆

    数组形式表示

    父节点和子节点的关系:

    i 的左子节点:2i+1 ,右子节点:2i+2

    i 的父节点:(i-1)/2

    i 是从 0 开始的

    再将上图的堆转换为数组的形式,如下图:

     这就是一个最大堆的数组表示形式。

    在数组中快速创建堆

    也就是怎么把任意一个数组变成最大/小堆。

    我们先把堆的最小单位拿出来,如下图:

    他不是一个最大堆,如果要变成最大堆,只需要父节点是95,子节点分别是86、88就可以了(86和95交换)。而一个最大堆是由若干个这个最小单位组成的,所以第一步就是将所有的堆的最小单位变成最大堆。

    1、首先先找到最后一个节点的父节点,找出该节点的最大子节点与自己比较,如果大于自身,就交换两个节点。

    2、继续移动到上一个父节点(也就是下标 -1 的地方),重复做第一步的比较操作,直到遍历所有的父节点。

    当我们移动完所有的父节点,那最大堆就形成了吗?还疏忽了一个地方。例如当移动到某个父节点时,如下图:

    最开始父节点是88,与子节点95交换了,那父节点就是95,95 的子节点就是 88,那88一定大于他的子节点吗?很显然这个答案是不一定,因为 88 的子节点只满足小于之前的父节点 95,所以还需要向下调整,直到子节点都小于父节点。

    3、对每次移动中,变成子节点的节点,向下调整,也就是判断他与子节点是否满足最大堆的特点,不满足还要继续移动节点(向下调整),满足的话就接着下个父节点。

    4、所有的节点交换完毕,最大堆构建完成。

    堆的算法实现

    堆数据结构的定义

    1. #define DEFAULT_CAPCITY 120 //默认的堆容量
    2. typedef struct _Heap
    3. {
    4. int* arr; //存储堆元素的数组
    5. int size; //堆中元素的个数
    6. int capcity; //堆的容量
    7. }Heap;
    8. //函数声明
    9. void buildHeap(Heap& heap);
    10. bool inset(Heap& heap, int value);
    11. bool initHeap(Heap& heap, int* orginal, int size);
    12. void adjustDown(Heap& heap, int i);
    13. void adjustUp(Heap& heap, int i);

    堆的初始化 

    1. bool initHeap(Heap& heap,int *orginal,int size)
    2. {
    3. //orginal 是指向数组的指针,而这个数组是我们要传入堆的数组
    4. int capcity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size; //size和默认容量的最大值
    5. heap.arr = new int[capcity];
    6. if (!heap.arr) return false; //申请失败
    7. heap.capcity = capcity;
    8. if (size > 0) //size合法
    9. {
    10. memcpy(heap.arr, orginal, sizeof(int) * size);
    11. heap.size = size;
    12. //建堆
    13. buildHeap(heap);
    14. }
    15. return true;
    16. }

    堆的创建

    1. //建堆,从最后一个父节点逐个向前调整所有的父节点(直到根节点),确保每一个父节点都是一个最大堆
    2. //那么,整体上就是一个最大堆
    3. void buildHeap(Heap& heap)
    4. {
    5. int i = (heap.size - 2) / 2; //因为下标从0开始,heap.size-1就得到下标,再结合公式就是这个式子
    6. for (; i >= 0; i--)
    7. {
    8. adjustDown(heap, i); //向下调整包含了构建最大堆,如果感到困惑,先看向下调整函数
    9. }
    10. }

    堆的向下调整函数

    1. void adjustDown(Heap& heap, int i)
    2. {
    3. int temp = heap.arr[i]; //保存父节点的键值
    4. int parent = 0 ,child = 0;
    5. for (parent = i; (2 * parent + 1) < heap.size; parent = child)
    6. {
    7. child = 2 * parent + 1; //先指向左子节点
    8. //指向两个子节点中最大的节点
    9. if (child + 1 < heap.size && heap.arr[child] < heap.arr[child + 1])
    10. {
    11. child = child + 1;
    12. }
    13. if (temp >= heap.arr[child])
    14. {
    15. break; //无需向下调整
    16. }
    17. else
    18. {
    19. heap.arr[parent] = heap.arr[child];
    20. heap.arr[child] = temp;
    21. }
    22. }
    23. }

    堆的插入新元素

    1、插入新的元素到最大堆的尾部,也就是数组的后面

    2、插入的元素可能会破环这个最大堆,需要重新调整,和父节点比较,如果比父节点大,就交换两个节点……重复直到新节点比父节点小或者新节点变为根节点(调整到位)。

    设计两个函数,一个是插入,一个是向上调整。

    1. bool insert(Heap& heap, int value)
    2. {
    3. if (heap.size == heap.capcity) //堆空间不足
    4. {
    5. return false;
    6. }
    7. int i = heap.size ; //指向新加元素的下标
    8. heap.arr[heap.size++] = value;
    9. adjustUp(heap , i);
    10. return true;
    11. }
    1. void adjustUp(Heap& heap, int i)
    2. {
    3. if (i <= 0 || i >= heap.size) return;
    4. while (i > 0)
    5. {
    6. int parent = (i - 1) / 2;
    7. if (parent >= 0) // 父节点没越界
    8. {
    9. if (heap.arr[parent] < heap.arr[i])
    10. {
    11. int temp = heap.arr[i];
    12. heap.arr[i] = heap.arr[parent];
    13. heap.arr[parent] = temp;
    14. i = parent;
    15. }
    16. else
    17. {
    18. break; //无需调整
    19. }
    20. }
    21. else
    22. {
    23. break; //父节点出界
    24. }
    25. }
    26. }

    看到这,你会发现堆的创建还有一种方式,也就是将数组的元素一个一个插入,也能得到最大堆。

    源代码

    1. #include <iostream>
    2. using namespace std;
    3. #define DEFAULT_CAPCITY 120 //默认的堆容量
    4. typedef struct _Heap
    5. {
    6. int* arr; //存储堆元素的数组
    7. int size; //堆中元素的个数
    8. int capcity; //堆的容量
    9. }Heap;
    10. void buildHeap(Heap& heap);
    11. bool insert(Heap& heap, int value);
    12. bool initHeap(Heap& heap, int* orginal, int size);
    13. void adjustDown(Heap& heap, int i);
    14. void adjustUp(Heap& heap, int i);
    15. //初始化堆
    16. bool initHeap(Heap& heap,int *orginal,int size)
    17. {
    18. //orginal 是指向数组的指针,而这个数组是我们要传入堆的数据
    19. int capcity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size; //size和默认容量的最大值
    20. heap.arr = new int[capcity];
    21. if (!heap.arr) return false;
    22. heap.capcity = capcity;
    23. if (size > 0)
    24. {
    25. memcpy(heap.arr, orginal, sizeof(int) * size);
    26. heap.size = size;
    27. //建堆
    28. buildHeap(heap);
    29. }
    30. return true;
    31. }
    32. //建堆,从最后一个父节点逐个向前调整所有的父节点(直到根节点),确保每一个父节点都是一个最大堆
    33. //那么,整体上就是一个最大堆
    34. void buildHeap(Heap& heap)
    35. {
    36. int i = (heap.size - 2) / 2; //因为下标从0开始,heap.size-1就得到下标
    37. for (; i >= 0; i--)
    38. {
    39. adjustDown(heap, i);
    40. }
    41. }
    42. void adjustDown(Heap& heap, int i)
    43. {
    44. int temp = heap.arr[i]; //父节点的键值
    45. int parent = 0 ,child = 0;
    46. for (parent = i; (2 * parent + 1) < heap.size; parent = child)
    47. {
    48. child = 2 * parent + 1;
    49. //指向两个子节点中最大的节点
    50. if (child + 1 < heap.size && heap.arr[child] < heap.arr[child + 1])
    51. {
    52. child = child + 1;
    53. }
    54. if (temp >= heap.arr[child])
    55. {
    56. break; //无需向下调整
    57. }
    58. else
    59. {
    60. heap.arr[parent] = heap.arr[child];
    61. heap.arr[child] = temp;
    62. }
    63. }
    64. }
    65. //堆——插入新元素
    66. bool insert(Heap& heap, int value)
    67. {
    68. if (heap.size == heap.capcity)
    69. {
    70. return false;
    71. }
    72. int i = heap.size ;
    73. heap.arr[heap.size++] = value;
    74. adjustUp(heap , i);
    75. return true;
    76. }
    77. void adjustUp(Heap& heap, int i)
    78. {
    79. if (i <= 0 || i >= heap.size) return;
    80. while (i > 0)
    81. {
    82. int parent = (i - 1) / 2;
    83. if (parent >= 0) // 父节点没越界
    84. {
    85. if (heap.arr[parent] < heap.arr[i])
    86. {
    87. int temp = heap.arr[i];
    88. heap.arr[i] = heap.arr[parent];
    89. heap.arr[parent] = temp;
    90. i = parent;
    91. }
    92. else
    93. {
    94. break; //无需调整
    95. }
    96. }
    97. else
    98. {
    99. break; //父节点出界
    100. }
    101. }
    102. }
    103. int main(void)
    104. {
    105. Heap heap;
    106. int orginalArr[] = { 1,2,3,87,93,82,92,86,95 };
    107. if (!initHeap(heap, orginalArr, sizeof(orginalArr) / sizeof(int)))
    108. {
    109. cout << "初始化堆失败!" << endl;
    110. exit(-1);
    111. }
    112. for (int i = 0; i < heap.size; i++)
    113. {
    114. printf("%d\n",heap.arr[i]);
    115. }
    116. puts("");
    117. insert(heap, 100);
    118. for (int i = 0; i < heap.size; i++)
    119. {
    120. printf("%d\n", heap.arr[i]);
    121. }
    122. return 0;
    123. }
  • 相关阅读:
    如何使用 PHP 和 MySQL 创建分页
    图像超分辨率重构实战
    使用svm-svc算法对乳腺癌进行预测
    CG-05 角度传感器工作介绍
    MybatisPlus 3 DQL 编程控制 3.2 查询投影
    一种图神经网络架构:GraphSAGE
    java基于ssm+vue+elementui的足球联赛会报名系统
    教资笔记(目录)
    C基本语法
    第一节:vue3 配置路由
  • 原文地址:https://blog.csdn.net/qq_66805048/article/details/133912189