1.什么是堆？
堆是一种数据结构，底层是一种数组对象，它可以被视为一棵完全二叉树结构
最大堆：每个父节点的都大于孩子节点； 最小堆：每个父节点的都小于孩子节点。
2.堆数据结构二叉树存储。
如图所示是个大堆，只能保证父节点比孩子节点大。所以下标为0是整个堆最大的，但无法确定下标为1,2的数据哪个更大
3.堆数据结构和优先级队列的代码实现
思想：从第一个非孩子节点的下标开始向下调整，保证父节点大于子节点否则交换。（大堆），小堆与之相反，所以，这里用到仿函数和模板的模板参数，使得代码能够复用，根据传的参数决定是大堆还是小堆，此处就体现出了c++的优势。若是C的话，这里只能老老实实把相似的代码再写一遍。
#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
template<class T>
struct Grearer
{
bool operator()(const T& left,const T& right)
{
return left > right;
}
};
template<class T>
struct Less
{
bool operator()(const T& left,const T& right)
{
return left < right;
}
};
template<class T,class Compare=Grearer<T>> //模板的模板参数，默认值为大于
class Heap
{
public:
Heap()
{}
Heap(T* a,size_t size) //建堆
{
for (size_t i = 0; i < size; i++) //数组内容拷贝给成员_a
{
_a.push_back(a[i]);
}
for (int i = (size - 2) / 2; i >= 0; i--) //从最后一个非叶子节点向下调整
{
_AjustDown(i);
}
}
void Push(const T& x)
{
_a.push_back(x); //先插到堆的最后一个位置
_AjustUp(_a.size() - 1); //再对最后一个数据向上进行调整
}
void Pop()
{
assert(!_a.empty()); //对空堆进行断言
swap(_a[0],_a[_a.size() - 1]); //交换堆的第一个数据和最后一个
_a.pop_back(); //相当于删除了第一个数据
_AjustDown(0); //对刚放在首位置的数据进行向下调整
}
size_t Size() //堆节点个数
{
return _a.size();
}
const T& Top() //堆的首个数据
{
return _a[0];
}
bool Empty() //堆是否为空
{
return _a.empty();
}
protected:
void _AjustUp(int root) //向上调整
{
size_t child = root;
size_t parient = (child - 1) / 2;
while (child > 0)
{
Compare com;
//if (_a[child] > _a[parient])
if (com(_a[child],_a[parient]))
{
swap(_a[child],_a[parient]);
}
else
{
break;
}
child = parient;
parient = (child - 1) / 2;
}
}
void _AjustDown(int root) //向下调整
{
size_t parient = root;
size_t child = 2 * parient + 1;
while (child<_a.size())
{
Compare com;
if ((child+1<_a.size())&&com(_a[child + 1],_a[child])) //此处一定要先考虑到右孩子不存在的情况
{
++child;
}
//if (_a[parient] < _a[child])
if (com(_a[child],_a[parient]))
{
swap(_a[parient],_a[child]);
}
parient = child;
child = 2 * parient + 1;
}
}
private:
vector<T>_a;
};
template<class T,class Compare=Grearer<T>>
class PriorityQueue //优先级队列
{
public:
void Push(const T&x)
{
_h.Push(x);
}
void Pop()
{
_h.Pop();
}
size_t Size()
{
return _h.Size();
}
const T& Top()
{
return _h.Top();
}
bool Empty()
{
return _h.Empty();
}
private:
Heap<T,Compare> _h;
};
void test()
{
int a[10] = { 10,16,18,12,11,13,15,17,14,19 };
Heap<int,Less<int>> hp(a,10);
hp.Push(30);
hp.Pop();
}
void TestPriority() //测试优先级队列
{
PriorityQueue<int> pq;
pq.Push(3);
pq.Push(2);
pq.Push(1);
pq.Push(9);
cout << pq.Top() << endl;
cout << pq.Size() << endl;
pq.Pop();
<h2>}
</h2>
4.堆排序
为什么要使用堆排序呢，因为它的时间复杂度只有O(N*lgN)，是一种比较好的排序算法。
以升序为例，基本思想：建好大堆后，把堆的第一个数据的堆的最后一个数据交换，则最后一个位置放置了整个堆中最大的数，此时除了下表为0的数据，剩下的满足大堆，再对剩下的堆进行向下调整（不包括最后一个数据），再把下标为0的数据和堆的倒数第二个数据进行交换，以此类推，最后得到一个有序的数组。
降序反之，建立小堆。算法类似。
升序的代码实现：
#pragma once
#include<iostream>
using namespace std;
void _AjustDown(int* a,size_t size,int root)
{
size_t parient = root;
size_t child = 2 * parient + 1;
while (child<size)
{
if ((child + 1<size) && (a[child + 1]> a[child])) //此处一定要先考虑到右孩子不存在的情况
{
++child;
}
if (a[parient] < a[child])
{
swap(a[parient],a[child]);
}
parient = child;
child = 2 * parient + 1;
}
}
void HeapSort(int* a,size_t size)
{
for (int i = (size - 2) / 2; i >= 0; i--) //建好一个大堆
{
_AjustDown(a,size,i);
}
for (size_t i = 0; i < size; i++)
{
swap(a[0],a[size - 1-i]); //把小标为0的数放在堆的倒数i+1结点处
_AjustDown(a,size - 1 - i,0); //调整除了最后一个数字的剩下的堆。
}
//return a;
}
void TestHeapSort()
{
int a[10] = { 10,19 };
HeapSort(a,10);
}
5.堆的另一种应用——大数据运算
如1亿个数中找出最大的前100个数 （1亿内存放不下）。
类似的题就可以用堆来解决。从1亿数中取出100个数建立一个100数的小堆，从硬盘一个个读取数据，若读出的数比下标为0（堆里最小的数）大，则插入堆，否则丢弃，最后这100个数据的堆保存的就是这1亿个数里面最大的前100个。
