堆一般指二叉堆,结构如下
圈内数字指下标,圈外为内容,如图现在并不能称为一个堆,因为它并不满足大堆也不满足小堆的组成,下面介绍大堆和小堆的简答介绍和实现
大堆是指每个父节点的数都大于自己的每个孩子节点的值
用到的算法是让大数上移循环至完成大堆
- void Adjustup(size_t child)
- {
- Compare<T> com;
- size_t parent =(child-1)/2;
- while(child>0)
- {
- if(com(_a[child],_a[parent]))
- {
- swap(_a[parent],_a[child]);
- child=parent;
- parent=(child-1)/2;
- }
- else
- {
- break;
- }
- }
- }
过程如下图
第一次交换33和43;
第二次交换43和12;
第三次交换33和12;
第四次交换23和8;
小堆的算法如下,采用大数向下循环转换
- void Adjustdown(size_t parent)
- {
- size_t child =parent*2+1;
- while(child<_a.size())
- {
- Compare<T> com;
- if(child+1<_a.size()&&com(_a[child+1],_a[child]))
- {
- ++child;
- }
- if(com(_a[child],_a[parent]))
- {
- swap(_a[parent],_a[child]);
- parent=child;
- child=parent*2+1;
- }
- else
- {
- break;
- }
- }
- }
循环如下
第一次交换33和5,
第二次交换12和5,
第三次交换4和8,
第四次交换5和4
堆排序算法如下
- void HeapSort(T* a,size_t size)
- {
- _a.reserve(size);
- for(size_t i=0;i<size;i++)
- {
- _a.push_back(a[i]);
- }
- for(int i=(_a.size()-2)/2;i>=0;--i)
- {
- Adjustdown(i);
- }
- print(_a,size);
- }
全部代码
测试用例
- #include <iostream>
- #include <assert.h>
- #include<stdlib.h>
- #include <vector>
- using namespace std;
- template<typename T>
- struct Big
- {
- bool operator()(const T& l,const T& r)
- {
- return l>r;
- }
- };
- template<typename T>
- struct Less
- {
- bool operator()(const T& l,const T& r)
- {
- return l<r;
- }
- };
- template<class T,template<class> class Compare>
- class Heap//二叉堆
- {
- public:
- Heap()
- {}
- void HeapSort(T* a,size);
- }
- void Adjustup(size_t child)
- {
- Compare<T> com;
- size_t parent =(child-1)/2;
- while(child>0)
- {
- if(com(_a[child],_a[child]);
- child=parent;
- parent=(child-1)/2;
- }
- else
- {
- break;
- }
- }
- }
- void Adjustdown(size_t parent)
- {
- size_t child =parent*2+1;
- while(child<_a.size())
- {
- Compare<T> com;
- if(child+1<_a.size()&&com(_a[child+1],_a[child]);
- parent=child;
- child=parent*2+1;
- }
- else
- {
- break;
- }
- }
- }
- bool Empty()
- {
- return _a.size()==0;
- }
- T& top()
- {
- assert(!_a.empty());
- return _a[0];
- }
- void Push(const T& x)
- {
- _a.push_back(x);
- size_t _size=_a.size();
- Adjustup(_size-1);
- print(_a,_size);
- }
- void Pop()
- {
- size_t _size=_a.size();
- assert(_size>0);
- swap(_a[0],_a[_size-1]);
- _a.pop_back();
- _size=_a.size();
- Adjustdown(0);
- print(_a,_size);
- }
- void print(vector<T> a,size_t size)
- {
- for(int i=0;i<size;i++)
- {
- cout<<a[i]<<" ";
- }
- cout<<endl;
- }
- private:
- vector<T> _a;
- };
- void test()
- {
- int Tree[]={23,12,33,45,15,46,17,78,59};
- Heap<int,Big> h1;
- h1.HeapSort(Tree,sizeof(Tree)/sizeof(Tree[0]));
- }
- void test2()
- {
- int arr[] = { 12,10,43,23,22,67,9 };
- Heap<int,Big> h1;
- h1.HeapSort(arr,sizeof(arr)/sizeof(arr[0]));
- Heap<int,Less> h2;
- h2.HeapSort(arr,sizeof(arr)/sizeof(arr[0]));
- }