堆的实现
堆数据结构是一种数组对象，它可以被视为一颗完全二叉树结构。
堆结构的二叉存储是
最大堆：每个父节点大于左右孩子节点
最小堆：每个父节点小于左右孩子节点
实现的基本接口
#include<vector>
template<class T>
class Heap
{
public:
Heap()//无参构造函数,若开始堆是空的则调用
{}
Heap(T* a, size_t n)//带参构造函数
{
_a.reserve(n);
for (size_t i = 0; i < n; ++i)
{
_a.push_back(a[i]);
}
//建堆
for (int i = (_a.size() - 2) / 2; i >= 0; --i)
{
AdjustDown(i);
}
}
void Push(const T& x)//时间复杂度logn
{
_a.push_back(x);
AdjustUp(_a.size() - 1);
}
void Pop()//使得根消失，剩下的仍是大堆,时间复杂度logn
{
swap(_a[0], _a[_a.size() - 1]);
_a.pop_back();
AdjustDown(0);
}
bool Empty()
{
return _a.empty();
}
size_t Size()
{
return _a.size();
}
const T& Top()//取堆里的数据，返回一个对象，出了作用域对象还存在
{
return _a[0];
}
void Print(int* a, int k)//打印
{
for (int i = 0; i < k; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
protected:
/*T* a;
size_t _size;
size_t _capacity;*/
vector<T> _a;
};
向下调整算法建大堆：
第一步：找到最后一个非叶子节点
第二步：找出当前节点的左右孩子中较大的一个节点（右孩子若存在则比较，否则不比较），让child指向该节点
第三步：如果当前节点小于child就交换，下调，将孩子给父亲，孩子节点下移
第四步：若不满足，则直接break。
void AdjustDown(size_t root)//建大堆：向下调整算法，时间复杂度：n*log2n
{
size_t parent = root;
size_t child = parent * 2 + 1;
while (child < _a.size())//child存在
{
if ((child + 1<_a.size()) && (_a[child + 1] > _a[child]))//若child+1存在，则选左右孩子大的
{
++child;
}
//此时拿到的孩子是大的
if (_a[child] > _a[parent])//若孩子比父亲大，则交换，且进行下一次调整
{
swap(_a[child], _a[parent]);
parent = child;
child = parent * 2 + 1;
}
else//大孩子小于父亲，则不需要调整
{
break;
}
}
}
向上调整算法：
第一步：上调，穿当前节点令其为孩子节点，上一节点为父节点。
第二步：若父节点小于当前节点，则交换；下调，将父亲给孩子，父亲节点上移
第三步：若不满足，则直接break。
void AdjustUp(size_t child)//向上调整算法，使得加一个数还是可调整成大堆,
{
size_t parent = (child - 1) / 2;
while (child>0)//若child小于0则调整终止
{
if (_a[child] > _a[parent])
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
测试：
void TestHeap()
{
int a[] = { 10, 9, 13, 21, 18, 12, 11, 8, 14, 15 };
Heap<int> hp1;//调用无参构造函数
Heap<int> hp2(a, sizeof(a) / sizeof(int));
hp2.Push(19);
hp2.Pop();
}
push 19后的结果：
pop 21后的结果
建立大堆与小堆的基本思想是一致的，利用仿函数可直接创建大堆或小堆
#include<vector>
template<class T>
struct Less
{
bool operator()(const T& l, const T& r)
{
return l < r;
}
};
template<class T>
struct Greater
{
bool operator()(const T& l, const T& r)
{
return l > r;
}
};
template<class T,class Compare>
class Heap
{
public:
Heap()//无参构造函数,若开始堆是空的则调用
{}
Heap(T* a, size_t n)//带参构造函数
{
_a.reserve(n);
for (size_t i = 0; i < n; ++i)
{
_a.push_back(a[i]);
}
//建堆
for (int i = (_a.size() - 2) / 2; i >= 0; --i)
{
AdjustDown(i);
}
}
void Push(const T& x)//时间复杂度logn
{
_a.push_back(x);
AdjustUp(_a.size() - 1);
}
void Pop()//使得根消失，剩下的仍是大堆,时间复杂度logn
{
swap(_a[0], _a[_a.size() - 1]);
_a.pop_back();
AdjustDown(0);
}
bool Empty()
{
return _a.empty();
}
size_t Size()
{
return _a.size();
}
const T& Top()//取堆里的数据，返回一个对象，出了作用域对象还存在
{
return _a[0];
}
protected:
void AdjustUp(size_t child)//向上调整算法，使得加一个数还是可调整成大堆,时间复杂度log2n
{
Compare com;
size_t parent = (child - 1) / 2;
while (child>0)//若child小于0则调整终止
{
if (com(_a[child] , _a[parent]))
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(size_t root)//建大堆：向下调整算法，时间复杂度：n*log2n
{
Compare com;
size_t parent = root;
size_t child = parent * 2 + 1;
while (child < _a.size())//child存在
{
if ((child + 1<_a.size()) && (com(_a[child + 1] , _a[child])))//若child+1存在，则选左右孩子大的
{
++child;
}
//此时拿到的孩子是大的
if (com(_a[child] , _a[parent]))//若孩子比父亲大，则交换，且进行下一次调整
{
swap(_a[child], _a[parent]);
parent = child;
child = parent * 2 + 1;
}
else//大孩子小于父亲，则不需要调整
{
break;
}
}
}
protected:
/*T* a;
size_t _size;
size_t _capacity;*/
vector<T> _a;
};
void TestHeap()//测试大堆的建立
{
int a[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
Heap<int, Greater<int> > hp2(a, sizeof(a) / sizeof(int));
hp2.Push(12);
hp2.Push(20);
hp2.Pop();
}
堆排序（选择排序）
升序建大堆，降序建小堆
（1）建堆
（2）选出最大数\最小数
（3）继续调整
代码实现：
#include<iostream>
using namespace std;
#include<assert.h>
void AdjustDowm(int *a, int k, int root)//建大堆
{
int parent = root;
int child = parent * 2 + 1;
while (child < k)
{
if ((child + 1 < k)
&&(a[child + 1] > a[child]))//选左右孩子大的
{
++child;
}
if (a[child]>a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int *a, int n)//堆排序
{
assert(a);
for (int i = (n - 2) / 2; i >= 0; --i)//大堆
{
AdjustDowm(a,n,i);
}
int end = n - 1;
while (end > 0)//交换
{
swap(a[0], a[end]);
AdjustDowm(a, end, 0);
--end;
}
}
void Print(int *a, int k)//打印
{
for (int i = 0; i < k; ++i)
{
cout << a[i] << " ";
}
cout << endl;
}
void TestHeap()
{
int a[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
int k = sizeof(a) / sizeof(int);
cout << "未排序的数据：" << " ";
Print(a, k);
cout << "排序后的数据：" << " ";
HeapSort(a, k);
Print(a, k);
}
int main()
{
TestHeap();
system("pause");
return 0;
}
输出的结果：