C++大小堆实现(仿函数)
具体代码如下
#pragma once
#include<iostream>
#include<vector>
using namespace std;
template<class T>
class Big
{
public:
bool operator()(T x, T y)
{
return x > y;
}
};
template<class T=int>
class Sma
{
public:
bool operator()(T x, T y)
{
return x < y;
}
};
template<class T,class Cmp>
class Heap
{
public:
Heap()
{}
Heap(const T* arr, size_t size)
{
for (int i = 0; i < size; ++i)
{
_heap.push_back(arr[i]);
}
int root = (_heap.size() - 2) / 2;//找到第一个非叶子结点
while (root>=0)
//向下调整
AdjustDown(root--);
}
void Push(T & t)
{
_heap.push_back(t);
AdjustUp(_heap.size() - 1);
}
void pop()
{
if (_heap.size() == 0)
return;
if (_heap.size() <= 2)
{
swap(_heap[0], _heap[_heap.size() - 1]);
_heap.pop_back();
}
else
{
swap(_heap[0], _heap[_heap.size() - 1]);
_heap.pop_back();
AdjustDown(0);
}
}
bool IsEmpty()const
{
return _heap.size() == 0;
}
const T & top() const
{
if (_heap.size() != 0)
return _heap[0];
else
throw exception("this is a bug");
}
protected:
void AdjustDown(int root)
{
//int child = root * 2 + 2 >= _heap.size() ? root * 2 + 1 : Cmp(_heap[root * 2 + 1], _heap[root * 2 + 2]) ? root * 2 + 1 : root * 2 + 2;
while (root <= (_heap.size() - 2) / 2)
{
int child = root * 2 + 2 >= _heap.size() ? root * 2 + 1 : Cmp()(_heap[root * 2 + 1], _heap[root * 2 + 2]) ? root * 2 + 1 : root * 2 + 2;
if (!Cmp()(_heap[root], _heap[child]))
{
swap(_heap[root], _heap[child]);
}
else
{
break;
}
root = child;
}
}
void AdjustUp(int child)
{
while (child >= 1)
{
int root = (child - 1) / 2;
if (!Cmp()(_heap[root], _heap[child]))
{
swap(_heap[root], _heap[child]);
}
child = root;
}
}
protected:
vector<T> _heap;
};
void test_heap()
{
int arr[] = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
Heap<int, Sma<int> >hp1(arr, 10);
int b = 3;
hp1.Push(b);
cout << "Over!" << endl;
while (!hp1.IsEmpty())
{
cout << hp1.top() << " ";
hp1.pop();
}
system("pause");
}
原文链接: https://www.cnblogs.com/lang5230/p/5309220.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/230708
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!