建站
咨询
售后
建站咨询
- 什么是堆
- 堆的实现
- 类的定义
- 构造函数
- 析构函数
- push
- 向上调整
- 判断堆是否为空
- 返回堆中有效数据个数
- 返回堆顶的数据
- pop数据,删除堆顶的数据
- 向下调整
- 堆的应用
- TopK问题
- 堆排序
- 1.第一种建堆方式-->向上调整
- 2.第二种建堆方式--->向下调整
- 排序
- 总结
注意大家在学习编程的过程中, 肯定听说过内存中的堆和栈以及静态区这种的, 这些是属于操作系统虚拟进程地址空间中的,
我们要说的堆和这个并不是一回事,堆是二叉树的一种, 是数据结构的一种,我们来看看吧
普通的二叉树不使用数组来存储,只有堆用数组来存储,
所以说堆的逻辑结构是二叉树, 物理结构是数组
如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储,在一个一维数组中，并满足：<= 且<= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点大的堆叫做大堆或大根堆，根节点最小的堆叫做最小堆或小根堆
堆的性质:
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
小堆: 子节点都比不小于父节点
大堆
堆的实现那我们尝试用数组来实现这种数据结构
类的定义那我们来分析一下堆这个类中需要哪些成员,
templateclass Heap
{public:
Heap();
void push(T val);
void pop();
T Top();
bool empty();
size_t size();
~Heap();
private:
T* _data;
int _top;//指向最后一个数据的下一个位置
int _capacity;
}; 默认构造就是把成员都初始化一下,我这里没有开默认空间, 大家可以选择开
Heap()
:_data(nullptr)
, _top(0)
, _capacity(0)
{}
析构函数进行资源清理,所以要把申请的空间都释放掉
~Heap()
{free(_data);
_top = _capactiy = 0;
}push就是插入一个数据,堆这里的插入和其他数据结构不同, 堆插入任何一个数据都要保证堆的特性, 不可以本来是堆,最后不是堆, 我们来分析一下,我们这里都以建大堆为例子
插入的代码比较简单,关键是向上调整,插入唯一需要注意的就是扩容的问题
void push(T val)
{//如果容量 == 个数
if (_capacity == _top)
{//扩容 -- >2倍扩容
int newCapacity = _capacity == 0 ? 4 : _capacity * 2;
T* ptr = (T*)realloc(_data, sizeof(T) * newCapacity);
if (nullptr == ptr)
{ perror("realloc fail");
exit(-1);
}
_capacity = newCapacity;
_data = ptr;
}
//扩容完毕
_data[_top] = val;
//++ 长度
++_top;
//向上调整
AdjustUp(_data, _top - 1);
}
为了保证堆的特性而向上调整,
那我们来分析一下这个向上调整该如何实现
void AdjustUp(T* data, int child)
{int parent = (child - 1) / 2;
while (child >0)
{ //这里是以大堆为例,如果孩子大于父亲, 那么就调整
if (data[child] >data[parent])
{ swap(data[child], data[parent]);
//迭代
child = parent;
parent = (child - 1) / 2;
}
else
{ break;
}
}这个相对比较简单
bool empty()
{//如果top等于0为空
return _top == 0;
}size_t size()
{return _top;
}首先要判断堆是否为空, 如果堆不为空, 还取个啥啊
T Top()
{assert(!empty());
return _data[_top - 1];
}我们来分析一下
void pop()
{assert(!empty());
//交换堆顶的数据和最后一个数据
swap(_data[0], _data[_top - 1]);
--_top;
//向下调整
AdjustDown(_data, n, 0);
}
核心思想就是如果大孩子大于根节点, 就交换,直到最后欧一层
void AdjustDown(T* data, int n, int parent)
{//先给出左孩子
int child = parent * 2 + 1;
while (child< n)
{ //如果右孩子存在,并且比左孩子大
if (child + 1< n && data[child + 1] >data[child])
child++;
if (data[child] >data[parent])
{ swap(data[child], data[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{ break;
}
}
}堆排序关于TopK问题,用堆解决是非常合适的问题,我之前写过一篇 TopK问题详解
堆排序是一种非常厉害的排序, 核心思想就利用了堆这种数据结构,我们来看看吧,我们距离
如果排升序的话,我们建小堆还是大堆呢??我们来分析一下
那我们该如何建堆呢?
插入建堆
int arr[] = {6,1,2,7,9,3,4,5,10,8 };
int len = sizeof(arr) / sizeof(int);
for (int i = 1; i< len; ++i)
{AdjustUp(arr, i);
}向下调整建堆就是二叉树的典型分治思想,我们来分析一下
int arr[] = {6,1,2,7,9,3,4,5,10,8 };
int len = sizeof(arr) / sizeof(int);
//建堆 最后一个节点的下标是len-1 ,所以它的父亲下标是(len-2)/2
for (int i = (len - 1 - 1) / 2; i >= 0; --i)
{AdjustDown(arr, len, i);
}
排序所以更推荐使用向下调整的方式来建堆,因为复杂度比较低
建好堆了以后就相对比较简单了,
利用堆的特性, pop的思想,把大的放到最后面, 然后调整前面的
void HeapSort(int* arr, int len)
{//建堆
for (int i = (len - 1 - 1) / 2; i >= 0; --i)
{AdjustDown(arr, len, i);
}
int end = len - 1;
while (end >0)
{swap(arr[0], arr[end]);
AdjustDown(arr, end, 0);
--end;
}
}建堆的复杂度O(N) , 调整的复杂度O(N* logN)
所以堆排序的复杂度就是O(N*logN)
总结堆还是非常常用的,一定要利用堆的特性, 后面的优先级队列还会涉及到,
感谢收看
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页题目：[数据结构]二叉树--堆-创新互联
分享链接：http://scgulin.cn/article/ceedce.html
