大佬教程收集整理的这篇文章主要介绍了【数据结构】堆,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
这里的堆不是指计算机里的“堆栈”,而是指一种数据结构,它的结构是一颗二叉树。
我们把一个关键码集合中所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足以下两个之一:
这里创建一个最小堆:
由于堆的每次插入都在已经建好的最小堆的后面插入,但插入之后,还需要对堆进行自下而上的调整。
堆的删除:从堆顶中删除堆顶元素。移除堆顶元素后,用堆的最后一个结点填补堆顶元素,并将元素个数减一,在对堆进行自上而下的调整。
下面是代码实现:
#include <iostream>
#include <vector>
using namespace std;
template <class T>
struct Less//小堆
{
bool operator()(const T& left,const T& right)
{
return left->_data < right->_data;
}
};
template <class T>
struct Greater//大堆
{
bool operator()(const T& left,const T& right)
{
return left > right;
}
};
template <class T,class Compare = Less<T>>
class Heap
{
public:
Heap()
{}
Heap(T *arr,size_t sizE)
{
_arr.resize(sizE);
for (size_t i = 0; i < size; i++)
_arr[i] = arr[i];
if (size > 1)
{
int root = (size - 2) / 2;//size_t的数据大于等于0造成死循环
for (; root >= 0; root--)
_AdjustDown(root);
}
}
void Push(const T& data)
{
_arr.push_BACk(data);
size_t size = _arr.size();
if (size > 1)
_Adjustup(size - 1);
}
void Pop()
{
size_t size = _arr.size();
if (_arr.empty())
return;
swap(_arr[0],_arr[size - 1]);
_arr.pop_BACk();
if (_arr.size() > 1)
_AdjustDown(0);
}
bool Empty()const
{
return _arr.empty();
}
size_t Size()const
{
return _arr.size();
}
T Top()const
{
return _arr[0];
}
private:
void _AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
size_t size = _arr.size();
while (child < sizE)
{
if (child + 1 < size && Compare()(_arr[child + 1],_arr[child]))
child += 1;
if (Compare()(_arr[child],_arr[parent]))
{
swap(_arr[parent],_arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void _Adjustup(size_t child)
{
size_t parent = (child - 1) / 2;
size_t size = _arr.size();
while (child > 0)
{
if (Compare()(_arr[child],_arr[child]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
private:
vector<T> _arr;
};
以上是大佬教程为你收集整理的【数据结构】堆全部内容,希望文章能够帮你解决【数据结构】堆所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。