C.删除 Heappop 向下调整 AdjustDown
1.删除的话，我们是要删除堆顶的数据，因为删除堆尾的数据并没有什么实际意义，删除就是让size--，但是堆顶数据的下标是0，所以在删除前应先交换堆顶和堆尾的数据；
2.删除完后，还要保持它还是个堆，不能把后面的顺序搞乱了，要想达到这个目的，就需要使用到向下调整这个函数；
3.假设是大堆，向下调整是父节点与其较大的子节点比较，如果较大的那个子节点大于父节点，则二者交换，然后较大的子节点成为了新的父节点，当子节点的下标大于或是等于节点总数，也就是size时，就结束循环。
D.堆的判空 Heapempty 堆顶数据 Heaptop 堆的大小 Heapsize
这些接口的实现都非常简单，博主就不在这里讲述了，可以参考后面的源码。
三.源码
Heap.h
1. #include <stdio.h> 2. #include <stdlib.h> 3. #include <assert.h> 4. #include <stdbool.h> 5. #include <time.h> 6. 7. #define MAX_MIN < //通过改变这里的符号，可以决定是建大堆还是小堆 8. 9. typedef int HPdatatype; 10. 11. typedef struct Heap 12. { 13. HPdatatype* arr; 14. int size; 15. int capacity; 16. }Heap; 17. 18. void Heapinit(Heap* php); 19. 20. void Swap(HPdatatype* p1, HPdatatype* p2); 21. 22. void AdjustUp(HPdatatype* arr, int child); //向上调整 23. 24. void Heappush(Heap* php, HPdatatype x); 25. 26. void AdjustDown(HPdatatype* arr, int parent, int n); //向下调整 27. 28. void Heappop(Heap* php); 29. 30. HPdatatype Heaptop(Heap* php); 31. 32. int Heapsize(Heap* php); 33. 34. bool Heapempty(Heap* php); 35. 36. void Heapdestroy(Heap* php);
Heap.c
1. #include "Heap.h" 2. 3. 4. void Heapinit(Heap* php) 5. { 6. assert(php); 7. 8. php->arr = (HPdatatype*)malloc(sizeof(HPdatatype) * 4); 9. if (php->arr == NULL) 10. { 11. perror("malloc fail"); 12. exit(-1); 13. } 14. php->size = 0; 15. php->capacity = 4; 16. } 17. 18. void Swap(HPdatatype* p1, HPdatatype* p2) 19. { 20. HPdatatype tmp = *p1; 21. *p1 = *p2; 22. *p2 = tmp; 23. } 24. 25. ///С 26. 27. void AdjustUp(HPdatatype* arr, int child) 28. { 29. assert(arr); 30. 31. int parent = (child - 1) / 2; 32. 33. while (child > 0) 34. { 35. if (arr[child] MAX_MIN arr[parent]) 36. { 37. Swap(&arr[child], &arr[parent]); 38. child = parent; 39. parent = (child - 1) / 2; 40. } 41. else 42. break; 43. } 44. } 45. 46. void Heappush(Heap* php, HPdatatype x) 47. { 48. assert(php); 49. 50. if (php->size == php->capacity) //插入前，判断数组是否已满 51. { 52. HPdatatype* tmp = (HPdatatype*)realloc(php->arr, 2 * sizeof(HPdatatype) * php->capacity); 53. if (tmp == NULL) 54. { 55. perror("realloc fail"); 56. exit(-1); 57. } 58. 59. php->arr = tmp; 60. php->capacity *= 2; 61. } 62. 63. php->arr[php->size] = x; 64. php->size++; 65. 66. AdjustUp(php->arr, php->size - 1); //这里要传size-1 67. } 68. 69. void AdjustDown(HPdatatype* arr, int parent, int n) 70. { 71. assert(arr); 72. 73. int child = 2 * parent + 1; 74. 75. while (child < n) 76. { 77. //判断较大（较小）的子节点 78. if ((child + 1) < n && arr[child + 1] MAX_MIN arr[child]) 79. { 80. child++; 81. } 82. 83. if (arr[child] MAX_MIN arr[parent]) 84. { 85. Swap(&arr[child], &arr[parent]); 86. parent = child; 87. child = 2 * parent + 1; 88. } 89. else 90. break; 91. } 92. } 93. 94. void Heappop(Heap* php) 95. { 96. assert(php); 97. assert(php->size); 98. Swap(&php->arr[0], &php->arr[php->size - 1]); 99. php->size--; 100. 101. AdjustDown(php->arr, 0, php->size); 102. } 103. 104. HPdatatype Heaptop(Heap* php) 105. { 106. assert(php); 107. assert(php->size); //为空时不能取数据 108. 109. return php->arr[0]; 110. } 111. 112. int Heapsize(Heap* php) 113. { 114. assert(php); 115. 116. return php->size; 117. } 118. 119. bool Heapempty(Heap* php) 120. { 121. assert(php); 122. 123. return php->size == 0; //size==0即为空 124. } 125. 126. void Heapdestroy(Heap* php) 127. { 128. assert(php); 129. free(php->arr); 130. php->arr = NULL; 131. php->size = 0; 132. php->capacity = 0; 133. }
test.c
1. #include "Heap.h" 2. 3. 4. void testHeap() 5. { 6. Heap hp; 7. Heapinit(&hp); 8. 9. int i = 0, n = 10; 10. int x = 0; 11. while (n) 12. { 13. x = rand() % 100 + 1; 14. 15. Heappush(&hp, x); 16. n--; 17. } 18. while (!Heapempty(&hp)) 19. { 20. printf("%d ", Heaptop(&hp)); 21. Heappop(&hp); 22. } 23. 24. printf("\n"); 25. Heapdestroy(&hp); 26. } 27. 28. int main() 29. { 30. srand((unsigned int)time(NULL)); 31. testHeap(); 32. 33. return 0; 34. }
🐲👻这循环队列的讲解就到这里了，若有错误或是建议欢迎小伙伴们指出。🐯🤖
🥰🤩希望小伙伴们可以多多支持博主哦。😍😃
😁😄谢谢你的阅读。😼😸
