因为堆(二叉堆)是一个完全二叉树，所以一般使用数组来存放
堆的性质
一句话来说就是父节点比子节点的数据要小(小顶堆，大顶堆反之)
为方便描述，以下皆以小顶堆为例进行说明
建立一个堆
假设表示堆的数组size为n，从最后一个非终端节点(即n/2)到根节点不断地根据堆的性质进行调整
根据堆的性质进行调整：
也就是让父节点上的数据小于子节点的数据，具体过程如下：
假设要调整的节点为s，且左子节点l、右子节点r都已经调整好
- 从s,l,r(如果有)中选取最小的节点(的索引)min
- 如果
s==min，则说明已经调整好，可以结束了- 否则交换s和min的数据，然后让s=min，再跳到第一步，递归的调整发生变动的子节点
堆排序
根据堆的性质，调整成堆的数组索引0处(堆顶)的数据为整个数组里最小的
堆排序简单来说就是
- 先将整个数组建立成一个堆
- 然后将堆顶与n-1处的数据交换
- 再以n=n-1为数组长度调整堆，直到n==0
不断重复后两个步骤，就会让最小的数依次挨到数组的右边去了
当然，小顶堆只能从大到小排序，要想从小到大排序，请使用大顶堆
参考代码
要点：
- 最后一个非终端节点 ----- n/2
- 左儿子节点 ------------- 2i+1
- 右儿子节点 ------------- 2i+2
- 父节点 ----------------- (i-1)/2
using namespace std;
struct Heap {
// 对应上文描述的‘根据堆的性质调整’
template <typename _T>
static void adjust(_T *h, int s, int n) {
do {
int l = left(s), r = right(s);
int min = s;
// Select minimal node from s, l, r
if (l < n && h[l] < h[s])
min = l;
if (r < n && h[r] < h[min])
min = r;
if (min == s)
break;
else // adjust child recursively
swap(h[min], h[s]), s = min;
} while (1);
}
// 对应上文的‘建立一个堆’
template <typename _T>
static void build(_T *h, int size) {
for (int i = size/2; i >= 0; i--)
adjust(h, i, size);
}
// 对应‘堆排序’
template <typename _T>
static void sort(_T *h, int size) {
build(h, size);
for (int i = size-1; i; --i)
swap(h[0], h[i]), adjust(g_heap, 0, i);
}
static inline int left(int n) { return 2*n+1; }
static inline int right(int n) { return 2*(n+1); }
static inline int parent(int n) { return (n-1)/2; }
};
