在二叉树中，我们用两种方法表示二叉树，一个是链表，一个是数组，但是数组比较适用于满二叉树或者完全二叉树。
堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。
堆结构的二叉树存储有两种方法：
最大堆：每个父节点的都大于孩子节点。
最小堆：每个父节点的都小于孩子节点。
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
template<class T>
class Heap
{
public:
Heap()//无参类型的构造函数
{}
Heap(T *a, size_t size)//有参类型的构造函数
{
assert(a);
for (size_t i = 0; i < size; i++)
{
_a.push_back(a[i]);
}
//建堆，用 向下调整 算法
//对于一个完全二叉树，其结点的父子关系与数组的下标的关系：
//左子下标= 父结点下标*2+1
//右子下标=父结点下标*2+2
for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒数第一个非叶子结点（最后一个元素一定是非叶子结点的子节点）
{
_AdjustDown(j);
}
/*
在第一次写时定义了j为size_t类型，由于j不管怎么运算都是无符号类型所以
j>=0并没有起到限制的作用，导致了死循环
*/
}
public:
void Push(const T &x)//在最后加入一个节点
{
_a.push_back(x);
_AdjustUp(_a.size() - 1);//向上调整，传入最后一个元素下标（调整x的位置）
}
void Pop()//把最大的删掉（根）
{
assert(!_a.empty());
swap(_a[0], _a[_a.size() - 1]);//把根节点和最后一个节点交换
_a.pop_back();//删掉最后一个节点
_AdjustDown(0);//向下调整
}
void Print()
{
for (size_t i = 0; i < _a.size(); i++)
{
cout << _a[i]<<" ";
}
cout << endl;
}
size_t size()
{
return _a.size();
}
bool empty()
{
return _a.empty();
}
protected:
void _AdjustDown(size_t parent)//时间复杂度O(log2(N))
{
size_t child = parent * 2 + 1; //找到其左孩子
while (child < _a.size())
{
if ((child + 1) < _a.size() && _a[child] < _a[child + 1])//若左孩子小于右孩子（且必须结点下标不超过范围）
{
++child;//指向大的
}
if (_a[child]>_a[parent])//若孩子大于父，则把大的放在父结点上
{
swap(_a[child], _a[parent]);
parent = child;//父和子调整后要继续向下调整交换后的子节点
child = parent * 2 + 1;//现在这个调整后的节点的子节点
}
else
break;
}
}
void _AdjustUp(size_t child)//时间复杂度O(log2(N))
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_a[child] > _a[parent])
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
private:
vector<T> _a;
};测试函数
void test()
{
int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
Heap<int> h2(a, 10);
h2.Push(3);
h2.Push(4);
h2.Print();
h2.Push(100);
h2.Print();
h2.Pop();
h2.Print();
h2.Pop();
h2.Print();
}
int main()
{
test();
getchar();
return 0;
}上面实现了最大堆，最小堆方法同最大堆，但是再在类中重新一遍则会使程序的可维护性降低，所以我们用仿函数来实现。
仿函数
仿函数就是使一个类使用看上去像一个函数，其实现就是类中实现一个operator().这个类就有了类似函数的行为。
struct Free{ void operator()(void *ptr) { free( ptr); }};void Testsharedptr(){int *p1=(int*)malloc(sizeof(int)*10);shared_ptr<int>sp1(p1,Free());//在使用完后自动释放p1}用仿函数实现最大堆与最小堆
template<class T>
struct Less
{
bool operator()(const T&left, const T&right)
{
return left < right;
}
};
template<class T>
struct Greater
{
bool operator()(const T&left, const T&right)
{
return left>right;
}
};
template<class T,class compare=Greater<T>>
class Heap
{
public:
Heap()//无参类型的构造函数
{}
Heap(T *a, size_t size)//有参类型的构造函数
{
assert(a);
for (size_t i = 0; i < size; i++)
{
_a.push_back(a[i]);
}
//建堆，用 向下调整 算法
//对于一个完全二叉树，其结点的父子关系与数组的下标的关系：
//左子下标= 父结点下标*2+1
//右子下标=父结点下标*2+2
for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒数第一个非叶子结点（最后一个元素一定是非叶子结点的子节点）
{
_AdjustDown(j);
}
}
public:
void Push(const T &x)//在最后加入一个节点
{
_a.push_back(x);
_AdjustUp(_a.size() - 1);//向上调整，传入最后一个元素下标（调整x的位置）
}
void Pop()//把最大的删掉（根）
{
assert(!_a.empty());
swap(_a[0], _a[_a.size() - 1]);//把根节点和最后一个节点交换
_a.pop_back();//删掉最后一个节点
_AdjustDown(0);//向下调整
}
void Print()
{
for (size_t i = 0; i < _a.size(); i++)
{
cout << _a[i]<<" ";
}
cout << endl;
}
size_t size()
{
return _a.size();
}
bool empty()
{
return _a.empty();
}
protected:
void _AdjustDown(size_t parent)//时间复杂度O(log2(N))
{
size_t child = parent * 2 + 1; //找到其左孩子
compare com;
while (child < _a.size())
{
if ((child + 1) < _a.size() && com(_a[child+1],_a[child]))
{
++child;
}
if (com(_a[child],_a[parent]))//
{
swap(_a[child], _a[parent]);
parent = child;//父和子调整后要继续向下调整交换后的子节点
child = parent * 2 + 1;//现在这个调整后的节点的子节点
}
else
break;
}
}
void _AdjustUp(size_t child)//时间复杂度O(log2(N))
{
size_t parent = (child - 1) / 2;
compare com;
while (child > 0)
{
if (com(_a[child] , _a[parent]))
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
private:
vector<T> _a;
}; 这样就实现了最大堆与最小堆，通过仿函数，程序的可维护性好于在类中写一个最大堆写法和最小堆写法。
测试
void test1()
{
int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
int b[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
Heap<int,Less<int>> h2(a, 10);//最小堆
h2.Push(3);
h2.Push(4);
h2.Print();
h2.Push(100);
h2.Print();
h2.Pop();
h2.Print();
h2.Pop();
h2.Print();
Heap<int>h3(b);//最大堆
h3.Push(3);
h3.Push(4);
h3.Print();
h3.Push(100);
h3.Print();
h3.Pop();
h3.Print();
h3.Pop();
h3.Print();
}堆的应用：
1.堆排序
分析：由于在大堆或者小堆排完后，只能保证每个小树为大堆或者小堆，故还需要进行排序才能使数组元素完全依次排列。
所以我们先用大堆排列后，使堆顶元素为大元素，再依次将堆顶元素和未交换的最后一个元素交换，交换完成后再将除了大的元素之外的元素进行交换
/******************************
堆排序
尽建立一个大堆，每次把堆顶的元素和最后一个还未交换的元素交换
*/
void AdjustDown(int *a, int parent, int size)
{
int child = parent * 2 + 1;
while (child < size)
{
if (a[child]<a[child + 1]&&child+1<size)
{
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--)
{
AdjustDown(a,i,n);//大堆向下调整
}
for (int i = 0; i < n; i++)
{
swap(a[n - 1 - i],a[0]);
AdjustDown(a, 0, n - 1 - i);
}
}2.求N个元素中前K个最大的数
分析：建立一个小堆存放前K个元素，小堆的堆顶元素为前K个中最小的值，剩下N-K个数中依次和堆顶元素相比较，若大于堆顶元素，入堆，每入堆一个元素再小堆排序一次，使堆顶元素总为这K个元素的最小值；若小于堆顶元素，则继续下一个数比较。当N-K个元素全比较完，堆中这K个元素就是最大的前K个数。
/*
从N个数中找到K个最大的数
建立一个小堆，大小为K,每次从第N-K的数据中取出一个和堆顶元素比较
*/
const int N = 1000000;
const int K = 100;
void AdjustDown(int *a, int parent, int size)
{
int child = parent * 2 + 1;
while (child <size)
{
if (child+1<size&&a[child] > a[child + 1])
{
child++;
}
if (a[child] < a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void GetTopK(int *a)
{
assert(K < N);
int top[100];
for (size_t i = 0; i < 100; i++)
{
top[i] = a[i];
}
//建一个小堆，向下调整
for (int i = (K - 2) / 2; i>=0; i--)
{
AdjustDown(top, i, K);
}
//从剩下的N-K的数据中拿数据和堆顶元素比较，若小于堆顶元素，则入堆
for (size_t j = K; j < N ; j++)
{
if (a[j]<top[0])
{
top[0] = a[j];
AdjustDown(top, 0, K);
}
}
}免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
