堆的插入和删除

x33g5p2x  于2021-09-19 转载在 其他  
字(1.2k)|赞(0)|评价(0)|浏览(484)

实现代码:

  1. #include<iostream>
  2. using namespace std;
  3. //堆的插入和删除
  4. //调整小根堆
  5. void HeapAdjust(int* nums, int idx, int n) {
  6. nums[0] = nums[idx]; //将要调整子树的根节点暂存在nums[0]位置处
  7. for (int i = 2 * idx;i <= n;i *= 2) {
  8. if (i<n && nums[i]>nums[i + 1])
  9. i++;
  10. if (nums[i] >= nums[idx]) { //如果父节点元素大于等于最小子结点的元素则停止循环,无需再往下进行比较
  11. break;
  12. }
  13. else {
  14. nums[idx] = nums[i];
  15. idx = i;
  16. }
  17. }
  18. nums[idx] = nums[0]; //将最初子树根节点元素存放在最终idx的位置
  19. }
  20. //往堆中插入一个元素
  21. void HeapInsert(int *nums,int n,int value) {
  22. nums[n] = value; //将要插入的元素放到堆底元素的下一个位置
  23. while (n > 1) { //不断向上进行判断父节点的元素是否大于要插入的元素,如果大于则逐步进行交换
  24. int pre = n / 2;
  25. if (nums[pre] <= nums[n]) { //如果父节点元素小于或等于要插入的元素,则停止往上判断
  26. break;
  27. }
  28. else {
  29. swap(nums[pre], nums[n]);
  30. }
  31. n /= 2;
  32. }
  33. }
  34. //删除堆中一个元素
  35. void HeapDelete(int* nums, int idx, int n) {
  36. swap(nums[idx], nums[n]); //将要删除的元素和堆底元素进行交换
  37. HeapAdjust(nums, idx, n - 1); //从删除位置往下开始调整堆
  38. }
  39. int main() {
  40. int nums[155],n;
  41. cin >> n;
  42. for (int i = 1;i <= n;i++) {
  43. cin >> nums[i];
  44. }
  45. //初步建立好的小根堆为:9 17 65 32 45 78 87 53
  46. HeapInsert(nums, n + 1, 13); //往堆中插入元素13
  47. n++; //数组长度加1
  48. cout << "插入元素13后的序列为:";
  49. for (int i = 1;i <= n;i++) {
  50. cout << nums[i] << " ";
  51. }
  52. cout << endl;
  53. HeapDelete(nums, 2, n); //删除堆中元素13
  54. n--; //数组长度减1
  55. cout << "删除元素13后的序列为:";
  56. for (int i = 1;i <= n;i++) {
  57. cout << nums[i] << " ";
  58. }
  59. cout << endl;
  60. return 0;
  61. }

运行结果:

在这里插入图片描述

相关文章