数据结构::堆
堆的定义及解释
专业定义：
如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
太复杂了，我们通俗一点理解。
一句话解释，堆是一颗完全二叉树，且堆只有大堆和小堆。
大堆：堆的每一个节点都比子节点大
小堆：堆的每一个节点都比子节点小
小堆：
大堆：
一道练习题，看看有没有掌握堆的定义
1.下列关键字序列为堆的是：（）
A 100,60,70,50,32,65
B 60,70,65,50,32,100
C 65,100,70,32,50,60
D 70,65,100,32,50,60
E 32,50,100,70,65,60
F 50,100,70,65,60,32
答案：A
堆的实现
堆既可以基于顺序结构实现，也可以基于链式结构实现。
但是，毕竟堆是一颗完全二叉树，根据完全二叉树的性质，这里采用顺序结构实现更加的简单
ps：完全二叉树的性质：
下标之间存在固定的关系
leftchild = parent * 2 + 1
leftchild = parent * 2 + 2
parent = (child - 1) / 2 --------//这里左右子节点下标通用
不清楚的同学可以下去自己画个图验证一下。
C++官方库主要实现了以下功能
这里是拿的priority_queue的成员函数，stl中priority_queue就是一个堆。
stl中priority使用了仿函数来实现了大小堆的自由切换，我们这里为了简单，就以大堆为例，库里面默认也是大堆。
感兴趣的同学，可以使用仿函数模拟实现一下库里面的priority_queue。
此外，库里面priority_queue采用了适配器的设计模式来实现，固然这更加的简单，高效，但是我们还是应该学会堆的原理，万一面试的时候，面试官让我们手撕一个堆，如果不会的话，面试直接就挂了。
首先，来看一下堆的成员
template<class T>
class Heap
{
private:
T* _heap;
size_t _size;
size_t _capacity;
public:
//构造析构
Heap(size_t size = 0, size_t capacity = 0);
~Heap();
//插入删除
void push(const T& val);
void pop();
//获取堆顶元素
T& top();
//size和empty
size_t size();
bool empty();
这里主要还是实现插入删除这两个函数，其余函数没有技术含量，等会直接看代码就行。
push函数
注：本博客以大堆为例。
单纯push非常的简单，难在哪里呢？
问题在于，我们在push之后，还需要保持数据结构依然是一个堆，要维护好堆的性质。
这里引入向上调整算法，AdjustUp()
基本原理就是，用子节点与父节点的数据相比较：
如果子节点更大，交换子节点和父节点的数据，维护一下下标，继续向上调整，知道子节点的下标到0；
如果父节点更大，就符合大堆的性质，直接不用继续比较了。
void AdjustUp(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_heap[parent] < _heap[child])
{
std::swap(_heap[parent], _heap[child]);
child = parent;
parent = (parent - 1) / 2;
}
else break;
}
}
插入的时候，先检查一下容量够不够，不够就扩容，然后尾插数据，接着size++，在使用AdjustUp维护好堆即可。
void push(const T& val)
{
if (_size == _capacity)//扩容
{
size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;
T* tmp = new T[newcapacity];
if(_heap)
for (size_t i = 0; i < newcapacity; i++)
{
tmp[i] = _heap[i];
}
_heap = tmp;
_capacity = newcapacity;
}
_heap[_size] = val;
_size++;
AdjustUp(_size - 1);
}
pop函数
pop函数的实现思路比push函数更加有意思。
堆的pop函数的作用是删除堆顶元素，不是尾删，不要闹出笑话，哈哈哈。
pop函数的思路是：
将堆顶元素与最后一个元素交换，size–
再采用AdjustDown算法维护堆
这个思路是非常巧妙的，要深刻体会一下，博主能力有限，没想出来很好的解释方法，对不住读者。
读者在读到这里的时候，不妨与自己的思路进行一下比较，体会一下这个思路的巧妙之处。
AdjustDown算法思路：
用父亲的下标确定子节点的下标，
选取两个节点中更大的那一个（如果有两个子节点的话）
父节点与该更大的子节点进行比较，
如果子节点更大，交换父子节点，并重新继续向下比较
如果父节点更大，结束算法
AdjustDown算法有几处细节需要注意：
a、只有两个子节点都存在时，才需要比较两个节点，有可能在最后一个叶子节点的时候，只有一个子节点
b、结束循环的条件，一个是父节点更大，另一个是，子节点的下标 >= size
//AdjustDown算法
void AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _size)
{
if (child + 1 < _size && _heap[child] < _heap[child + 1])
{
child++;
}
if (_heap[parent] < _heap[child])
{
std::swap(_heap[parent], _heap[child]);
parent = child;
child = child * 2 + 1;
}
else break;
}
}
//pop函数
void pop()
{
assert(_size > 0);
std::swap(_heap[0], _heap[_size - 1]);
_size--;//先删除，再向下调整
AdjustDown(0);
}
整体代码（仅供参考）
template<class T>
class Heap
{
private:
T* _heap;
size_t _size;
size_t _capacity;
public:
Heap(size_t size = 0, size_t capacity = 0)
:_size(size),_capacity(capacity)
{
_heap = nullptr;
}
~Heap()
{
delete[] _heap;
_size = _capacity = 0;
}
void AdjustUp(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_heap[parent] < _heap[child])
{
std::swap(_heap[parent], _heap[child]);
child = parent;
parent = (parent - 1) / 2;
}
else break;
}
}
void AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _size)
{
if (child + 1 < _size && _heap[child] < _heap[child + 1])
{
child++;
}
if (_heap[parent] < _heap[child])
{
std::swap(_heap[parent], _heap[child]);
parent = child;
child = child * 2 + 1;
}
else break;
}
}
void push(const T& val)
{
if (_size == _capacity)//扩容
{
size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;
T* tmp = new T[newcapacity];
if(_heap)
for (size_t i = 0; i < newcapacity; i++)
{
tmp[i] = _heap[i];
}
_heap = tmp;
_capacity = newcapacity;
}
_heap[_size] = val;
_size++;
AdjustUp(_size - 1);
}
void pop()
{
assert(_size > 0);
std::swap(_heap[0], _heap[_size - 1]);
_size--;//先删除，再向下调整
AdjustDown(0);
}
T& top()
{
return _heap[0];
}
size_t size()
{
return _size;
}
bool empty()
{
return _size == 0;
}
};
运行效果
测试代码：
运行结果：
提前祝大家中秋节快乐！！！
原文地址：https://blog.csdn.net/2303_78940834/article/details/142266013
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！