【数据结构】大小堆的实现及堆排序

前端之家收集整理的这篇文章主要介绍了【数据结构】大小堆的实现及堆排序前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

堆一般指二叉堆,结构如下


圈内数字指下标,圈外为内容,如图现在并不能称为一个堆,因为它并不满足大堆也不满足小堆的组成,下面介绍大堆和小堆的简答介绍和实现

大堆是指每个父节点的数都大于自己的每个孩子节点的值

用到的算法是让大数上移循环至完成大堆

  1. void Adjustup(size_t child)
  2. {
  3. Compare<T> com;
  4. size_t parent =(child-1)/2;
  5. while(child>0)
  6. {
  7. if(com(_a[child],_a[parent]))
  8. {
  9. swap(_a[parent],_a[child]);
  10. child=parent;
  11. parent=(child-1)/2;
  12. }
  13. else
  14. {
  15. break;
  16. }
  17. }
  18. }

过程如下图


第一次交换33和43;

第二次交换43和12;

第三次交换33和12;

第四次交换23和8;

小堆的算法如下,采用大数向下循环转换

  1. void Adjustdown(size_t parent)
  2. {
  3.  
  4. size_t child =parent*2+1;
  5. while(child<_a.size())
  6. {
  7. Compare<T> com;
  8. if(child+1<_a.size()&&com(_a[child+1],_a[child]))
  9. {
  10. ++child;
  11. }
  12. if(com(_a[child],_a[parent]))
  13. {
  14. swap(_a[parent],_a[child]);
  15. parent=child;
  16. child=parent*2+1;
  17. }
  18. else
  19. {
  20. break;
  21. }
  22. }
  23. }

循环如下


第一次交换33和5,

第二次交换12和5,

第三次交换4和8,

第四次交换5和4

堆排序算法如下

  1. void HeapSort(T* a,size_t size)
  2. {
  3. _a.reserve(size);
  4. for(size_t i=0;i<size;i++)
  5. {
  6. _a.push_back(a[i]);
  7. }
  8. for(int i=(_a.size()-2)/2;i>=0;--i)
  9. {
  10. Adjustdown(i);
  11. }
  12. print(_a,size);
  13. }

全部代码
  1. #include <iostream>
  2. #include <assert.h>
  3. #include<stdlib.h>
  4. #include <vector>
  5. using namespace std;
  6. template<typename T>
  7. struct Big
  8. {
  9. bool operator()(const T& l,const T& r)
  10. {
  11. return l>r;
  12. }
  13. };
  14. template<typename T>
  15. struct Less
  16. {
  17. bool operator()(const T& l,const T& r)
  18. {
  19. return l<r;
  20. }
  21. };
  22. template<class T,template<class> class Compare>
  23. class Heap//二叉堆
  24. {
  25.  
  26. public:
  27. Heap()
  28. {}
  29. void HeapSort(T* a,size);
  30. }
  31. void Adjustup(size_t child)
  32. {
  33. Compare<T> com;
  34. size_t parent =(child-1)/2;
  35. while(child>0)
  36. {
  37. if(com(_a[child],_a[child]);
  38. child=parent;
  39. parent=(child-1)/2;
  40. }
  41. else
  42. {
  43. break;
  44. }
  45. }
  46. }
  47. void Adjustdown(size_t parent)
  48. {
  49.  
  50. size_t child =parent*2+1;
  51. while(child<_a.size())
  52. {
  53. Compare<T> com;
  54. if(child+1<_a.size()&&com(_a[child+1],_a[child]);
  55. parent=child;
  56. child=parent*2+1;
  57. }
  58. else
  59. {
  60. break;
  61. }
  62. }
  63. }
  64. bool Empty()
  65. {
  66. return _a.size()==0;
  67. }
  68. T& top()
  69. {
  70. assert(!_a.empty());
  71. return _a[0];
  72. }
  73. void Push(const T& x)
  74. {
  75. _a.push_back(x);
  76. size_t _size=_a.size();
  77. Adjustup(_size-1);
  78. print(_a,_size);
  79. }
  80. void Pop()
  81. {
  82. size_t _size=_a.size();
  83. assert(_size>0);
  84. swap(_a[0],_a[_size-1]);
  85. _a.pop_back();
  86. _size=_a.size();
  87. Adjustdown(0);
  88. print(_a,_size);
  89. }
  90. void print(vector<T> a,size_t size)
  91. {
  92.  
  93. for(int i=0;i<size;i++)
  94. {
  95. cout<<a[i]<<" ";
  96. }
  97. cout<<endl;
  98. }
  99. private:
  100. vector<T> _a;
  101. };
测试用例
  1. void test()
  2. {
  3. int Tree[]={23,12,33,45,15,46,17,78,59};
  4. Heap<int,Big> h1;
  5. h1.HeapSort(Tree,sizeof(Tree)/sizeof(Tree[0]));
  6. }
  7. void test2()
  8. {
  9. int arr[] = { 12,10,43,23,22,67,9 };
  10. Heap<int,Big> h1;
  11. h1.HeapSort(arr,sizeof(arr)/sizeof(arr[0]));
  12. Heap<int,Less> h2;
  13. h2.HeapSort(arr,sizeof(arr)/sizeof(arr[0]));
  14. }

猜你在找的数据结构相关文章