堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
-
1.堆中某个节点的值总是不大于或不小于其父节点的值；
-
2.堆总是一棵完全树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
" ki<=k2i,ki<=k2i+1;或ki>=k2i,ki>=k2i+1.（i=1,2,…,[n/2])"
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
堆的基本思想其实也很简单，就是三个元素（父节点和俩个子节点）之间比较大小，若是最大堆，就是最大的那个数移到父节点；若是最小堆，就把最小的那个数移到父节点那个位置。
最小堆最大堆
对一个序列都经过这样的处理，序列的第一个就是最小（最小堆）的元素，然后把第一个元素移除，把最后一个元素复制过来，或者把第一个元素和最后一个元素交换，然后再对剩下的元素就行处理，直到整个序列处理完，序列就是一个有序的了。
对a[10] = {4, 1, 3, 5, 2, 6, 7, 0, 9, 8}进行一次处理：
1. 2.
3. 4.
5.
堆排序的大致过程就这样，然后就是0和8交换位置，再把总数减1，在进行上述过程。
c实现：
#include#include void fixDown(int *a, int numTotal, int pos){ int compareIndex = pos * 2 + 1;//左字节点的下标 while (2 * pos + 1 < numTotal) { compareIndex = 2 * pos + 1; if ((compareIndex + 1 < numTotal) && (a[compareIndex] > a[compareIndex + 1])) //左右子节点的最小的那个数的下标 compareIndex += 1; /* *父节点大于子节点的话，就交换，不然就break */ if (a[pos] > a[compareIndex]) { int temp = a[pos]; a[pos] = a[compareIndex]; a[compareIndex] = temp; } else break; pos = compareIndex;//向下继续比较 }}int main(void){ int a[10] = {4, 1, 3, 5, 2, 6, 7, 0, 9, 8}; int numTotal = sizeof(a) / sizeof(int); int i; /* *建一个堆 */ for (i = (numTotal - 1) / 2; i >= 0; i--) { fixDown(a, numTotal, i); } while (numTotal > 0) { /* *交换第一个和最后一个元素 */ int temp = a[0]; a[0] = a[numTotal - 1]; a[numTotal - 1] = temp; fixDown(a, --numTotal, 0); } for (i = 0; i < 10; i++) { printf("%d ", a[i]); } printf("\n"); return 0;}
c++模板实现：
#include#include #include #include using namespace std;template void adjust_heap(Randomiterator begin, Randomiterator end, Randomiterator pos, Comparator comp) { typedef typename std::iterator_traits ::difference_type diff_t; const diff_t numTotal = distance(begin, end); diff_t position = distance(begin, pos); while ((2 * position + 1 < numTotal)) { diff_t compIndex = 2 * position + 1; if ((compIndex + 1 < numTotal) && (comp(begin[compIndex], begin[compIndex + 1]))) compIndex += 1; if (comp(begin[compIndex], begin[position])) break; std::swap(begin[compIndex], begin[position]); position = compIndex; }}template void Heapsort(Randomiterator begin, Randomiterator end, Comparator comp){ typedef typename std::iterator_traits ::difference_type diff_t; diff_t numTotal = distance(begin, end); if (begin == end || begin + 1 == end) return; Randomiterator itr; for (itr = begin + (numTotal - 1)/2; itr >= begin; itr--) adjust_heap(begin, end, itr, comp); while (end - begin > 0) { std::swap(begin[0], begin[distance(begin, end - 1)]); adjust_heap(begin, --end, begin, comp); }}template void heapsort(Randomiterator begin, Randomiterator end) { Heapsort(begin, end, std::less ::value_type>());}int main(void){ int a[10] = {4, 1, 3, 5, 2, 6, 7, 0, 9, 8}; heapsort(&a[0], &a[10]); int i; for (i = 0; i < 10; i++) cout << a[i] << ' '; cout << endl;}