一、用模版实现大小堆
作为一家“创意+整合+营销”的成都网站建设机构，我们在业内良好的客户口碑。
创新互联建站提供从前期的网站品牌分析策划、网站设计、做网站、
网站设计、创意表现、网页制作、系统开发以及后续网站营销运营等一系列服务，帮助企业打造创新的互联网品牌经营模式与有效的网络营销方法,创造更大的价值。
如果不用模版的话，写大小堆，就需要分别实现两次，但是应用模版的话问题就简单多了，我们只需要实现两个仿函数，Greater和Less就行了，仿函数就是用类实现一个()的重载就实现了仿函数。这个看下代码就能理解了。再设计参数的时候，需要把模版设计成模版的模版参数，因为要实现大小堆嘛！当我们实现好一个大堆或者小队的逻辑后只需要用模版接收的Greater或Less类定义一个变量，就能实现通用功能了。
template
struct Less
{
bool operator()(const T& l, const T& r)
{
return l < r;
}
};
template
struct Greater
{
bool operator()(const T& l, const T& r)
{
return l>r;
}
};
template class compare = less>
class Heap
{
public:
Heap()
{}
Heap(T* a,size_t size)
{
size_t index = 0;
while (index < size)
{
_a.push_back(a[index]);
index++;
}
for (int i = (_a.size() - 2) / 2; i >= 0; i--)
_AdjustDown(i);
}
void push(const T& x)
{
_a.push_back(x);
_AdjustUp(_a.size() -1);
}
void pop()
{
size_t size = _a.size();
assert(size > 0);
swap(_a[0], _a[size - 1]);
_a.pop_back();
size = _a.size();
_AdjustDown(0);
}
size_t top()
{
assert(!_a.empty());
return _a[0];
}
bool empty()
{
return _a.size() == 0;
}
size_t Size()
{
return _a.size();
}
void Print()
{
for (int i = 0; i < _a.size(); i++)
{
cout << _a[i] << " ";
}
cout << endl;
}
protected:
void _AdjustUp(int child)
{
int 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;
}
}
}
void _AdjustDown(size_t parent)
{
size_t child = 2 * parent + 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[parent], _a[child]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
protected:
vector _a;
};
二、用模版实现优先级队列
前面实现了大小堆，这里我们可以使用适配器，直接调用大小堆，来实现优先级队列。
template class compare = Less>
class priorityQueue
{
private:
Heap _hp;
public:
void push(const T& x)
{
_hp.push(x);
}
void pop()
{
_hp.pop();
}
T& Top()
{
return _hp.top();
}
void Print()
{
_hp.Print();
}
};
三、堆排序的实现
堆排序的实现简单思路，(升序)先构造出来一个大堆，调整堆后，将堆头和最后一个数据交换，大值就换到了数组的最后，然后在调整堆，但是size需要减少1，因为大的已经调整到最后，如果再加上它调整又会回到堆头。
int*& HeapSort(int* a, size_t size)
{
for (int i = (size - 2) / 2; i >= 0; i--)
{
_AdjustDown(a, size, i);
}
for (int i = 0; i < size; i++)
{
swap(a[0], a[size - i - 1]);
_AdjustDown(a, size - i - 1, 0);
}
return a;
}另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网页标题：【数据结构】用模版实现大小堆、实现优先级队列，以及堆排序-创新互联
URL分享：
http://cdxtjz.cn/article/icoss.html
