堆：实质是一颗完全二叉树，最大堆的特点：父节点值均大于子节点；最小堆的父节点值均小于子节点；
一般使用连续内存存储堆内的值，因而可以根据当前节点的索引值推断子节点的索引值：
节点i的父节点为(i-1)/2；
节点j的左子结点：j * 2 + 1;
节点j的右子结点：j * 2 + 2;
以下代码实现了最大堆最小堆，当比较函数使用std::greater，得到最大堆，当比较函数使用std::less得到最小堆；
代码及测试用例如下：
//最大最小堆
//MaxMinHeap.h #pragma once
#include <assert.h> using namespace std; template <typename T>
void mswap(T &a, T &b)
{
T tmp = a;
a = b;
b = tmp;
} template <typename T,typename Compare = std::less<T>>
class MaxMinHeap
{
public:
int hSize ; //堆空间
int hCurNum;//堆内已占用空间
T *data; private:
Compare comp;//比较函数
public:
MaxMinHeap(int size)
{
hSize = size;
assert(hSize>);
data = new T[hSize];
hCurNum = ;
};
~MaxMinHeap(void)
{
if(data!=NULL)
delete []data;
}; void headAdd(T num)
{
if (hCurNum==hSize)
{
if (comp(num,data[]))//greater 大顶堆 保留最小的K个数；less 小顶堆 保留最大的K个数
return;
data[]=num;
HeapFixDown(,hCurNum);
}
else
{
data[hCurNum++]=num;
HeapFixUp(hCurNum-);
}
};
//最大堆排序后得到升序序列；最小堆排序后得到降序序列
void sort()
{
for (int i=hCurNum-; i >= ; --i)
{
mswap(data[i],data[]);
HeapFixDown(,i);
}
} void GetHnum(T &n)//获取最大堆的最小值或者最小堆的最大值
{
n = data[];
};
void HeapFixUp(int index)
{
assert (index < hCurNum);
T tmp=data[index];
int j = (index - )/;//父节点
while(j>= && index !=)
{
if(comp(data[j],tmp))
break;
data[index]=data[j];
index = j;
j = (index - )/;
}
data[index]=tmp;
}; //从节点index开始进行向下调整
void HeapFixDown(int index, int n)
{
assert(index<hCurNum);
assert(n<hCurNum); T tmp=data[index];
int j = index*+;
while(j<n)
{
if(j+ < n && comp(data[j+],data[j]))//大顶堆中左右孩子找最大的，小顶堆左右孩子找最小的
++j;
if(comp(tmp,data[j]))
break;
data[index]=data[j];
index = j;
j = index*+;
}
data[index]=tmp;
};
}; #include <functional>
#include <iostream>
#include "MaxMinHeap.h " using namespace std; int main(int argc , char ** argv)
{
MaxMinHeap<float,greater<float>> test(); for (int i = ;i < ; ++i)
{
test.headAdd(-i*+);
}
for (int i = ; i < ; ++i)
{
cout<<test.data[i]<<endl;
}
test.sort();
for (int i = ; i < ; ++i)
{
cout<<test.data[i]<<" ";
}
cout<<endl;
return ;
}