这篇文章主要介绍了编程开发中如何实现堆,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
一、堆的概念
堆数据结构是一种数组对象,它可以被视为一棵完全二叉树结构。
堆结构的二叉树存储是:
最大堆:每个父节点的都大于孩子节点。
最小堆:每个父节点的都小于孩子节点。
堆栈中的物体具有一个特性: 最后一个放入堆栈中的物体总是被最先拿出来, 这个特性通常称为后进先出(LIFO)队列。 堆栈中定义了一些操作。 两个最重要的是PUSH和POP。 PUSH操作在堆栈的顶部加入一 个元素。POP操作相反, 在堆栈顶部移去一个元素, 并将堆栈的大小减一。
在此,用vector容器来实现存储,vector容器是一个模板类,可以存放任何类型的对象(但必须是同一类对象)。vector对象可以在运行时高效地添加元素,并且vector中元素是连续存储的。当容量不够时,它能够自己去扩容。故我们在push数据时就不用考虑一些其他容量不足等等因素。
二、堆的实现
通过二叉树来实现堆的结构。
先实现一个compare,如果实现大小堆用对象调其对应类运算符“()”重载
template<class T>
struct Less
{
bool operator()(const T& l, const T& r)
{
return l < r;
}
};
template<class T>
struct Big
{
bool operator()(const T& l, const T& r)
{
return l > r;
}
};
先定义一个堆:
用模板的模板参数:
如:当 测试用例为:
int arr[] = { 12, 10, 43, 23, 22, 45, 67,9 };
Heap<int,Big> N(arr, sizeof(arr)/sizeof(arr[0]));
当你给定compare为Big时它会按照大堆去排序
Heap<int,Less> N(arr, sizeof(arr)/sizeof(arr[0]));
当你给定compare为Big时它会按照小堆去排序
template<class T , template<class> class compare > //模板的模板参数
class Heap
{
public:
Heap()
{}
Heap(T* a, size_t size)
{
_a.reserve(size);
for (size_t i = 0; i < size; ++i)
{
_a.push_back(a[i]);
}
//建堆
for (int i = (_a.size() -2)/2; i >= 0; --i)
{
_AdjustDown(i);
}
Disp(_a, size);
}
//Pop时,先将第一个与最后一个交换,(这样不至于打乱其他子堆的顺序),然后
//删除最后一个,再让它下调重新调整顺序
void Pop()
{
size_t _size = _a.size();
assert(_size > 0);
swap(_a[0], _a[_size-1]);
_a.pop_back();
_size = _a.size();
_AdjustDown(0);
Disp(_a, _size);
}
//push一个数据后,让其上调,以调整顺序
void Push(const T& x)
{
_a.push_back(x);
size_t _size = _a.size();
_AdjustUp(_size-1);
Disp(_a, _size);
}
T& Top()
{
assert(!_a.empty());
return _a[0];
}
bool empty()
{
return _a.size() == 0;
}
void Disp(vector<T> a, size_t k)//打印
{
for (size_t j = 0; j < k; j++)
{
cout << a[j] << " ";
}
cout << endl;
}
在建堆时,首先来定义一个下调函数_AdjustDown();用来调整已实现大小堆顺序。
实现思想:
1、找最后一个非叶子结点
2、如果当前结点的孩子结点左孩子大于右孩子,就让child指向最大孩子结点(在此必须满足存在右孩子)
3、如果当前结点小于孩子结点,就交换,下调,将孩子给父亲,孩子结点下移
4、不满足 就break;
void _AdjustDown(size_t parent) // 下调
{
size_t child = parent * 2 + 1;
while (child < _a.size())
{
compare<T> _com;
if ( child + 1 < _a.size()&&_com(_a[child + 1], _a[child]) )
{
++child;
}
if (_com(_a[child],_a[parent]))
{
swap(_a[child], _a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
再写一个上调函数_AdjustUp()当Push一个数时,让它上调,以调整整个堆的顺序。
实现思想:
1、上调,传当前结点,令当前节点为孩子结点,上一结点为父结点,
2、在这里不用考虑左右结点谁大谁小
3、如果孩子结点大于父亲结点,交换,上移
4、不满足 就break;
注意:在此不用考虑左右子数谁大谁小,上调是如果孩子结点比父结点大,那它肯定比兄弟结点大。
void _AdjustUp(size_t child) //上调
{
compare<T> _com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_com(_a[child], _a[parent]))
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
三、优先队列
template<class T, template<class> class compare = Big>//利用模板的模板参数
class PriorityQueue //优先队列
{
protected:
Heap<T, compare> _hP;
public:
void _push(const T& x)
{
_hP.Push(x);
}
void Pop()
{
_hP.Pop();
}
T& Top()
{
return _hP.Top();
}
};
测试用例:
PriorityQueue<int,Big> s;
s._push(3);
s._push(12);
s._push(5);
s._push(78);
s._push(43);
s._push(10);
s._push(32);
结果会以大堆形式实现为:
如果将测试用例改为:
PriorityQueue<int,Less> s;
s._push(3);
s._push(12);
s._push(5);
s._push(78);
s._push(43);
s._push(10);
s._push(32);
结果会以小堆实现 为:
感谢你能够认真阅读完这篇文章,希望小编分享的“编程开发中如何实现堆”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。