堆的实现【C++】
堆的实现
- 概念
- 实现
- 完整代码
概念
介绍堆之前得说一下二叉树，因为堆的逻辑结构是二叉树，二叉树的树的子集，树只有一个根节点，向下衍生出了很多节点，并且这个节点之间相互没有连接，除非是父子节点，如果有连接了那就是图；如果拥有很多独立不连接的树，这样的数据结构称之为森林。
如果对树作进一步的限制：每一个节点（包括根节点）最多只有两个子树，那么这样的树叫做二叉树，比如：
这种也是：
二叉树呢又可以分为完全二叉树和满二叉树：
完全二叉树就是每一个节点都有两个子树（子节点），例如：
满二叉树就是除了最后一层，也就是最底下的一层，其他的每层都是完全二叉树，并且最后一层的节点得从左到右存在，下面这种就属于满二叉树：
但是这种就不属于满二叉树：
堆的逻辑数据结构就是使用满二叉树实现的，为什么说是逻辑呢？这是因为我们在实际实现的时候使用的是数组来实现的，原因如下:
如果我们想使用数组来存储下面这个二叉树：
这样对吗？像这样写的话，岂不是没有二叉树的特点了，比如怎么判断左右子树呢？所以我们得从上到下，从左到右的添加进数组。
例如：
这样就可以轻松知道左右子树从而通过数组构建出二叉树了，但是这个数组的中间浪费了不少空间，如何避免呢？
那就是使用满二叉树。
数组中的任意一个节点怎么能够得到他的左右子节点和父节点呢？可以通过下面的几个公式：
如果想知道数组arr里面的节点i的左右子节点和父节点：
- 父节点=arr[(i-1)/2]
- 左节点=arr[i*2+1];
- 右节点=arr[i*2+2];
概念说完了，我们接下来可以用这种数据结构来构建一个大堆和小堆，大堆的特点是父节点一定大于子节点，但是左右节点没有讲究，小堆则相反。
利用大小堆可以实现topk问题，也就是求出一堆数据中第几大（小）的数是哪一个。也可以实现堆排序。
实现
先实现一个大堆：
然后就得插入数据：
每次插入数据都是插入到数组的最后面，也就是二叉树的最下一层的最右边，此时需要维护大堆的规则，也就是父节点的值大于子节点的值，由于每次插入时都是在最下面，所以如果不符合规则，当前插入的值大于父节点，我们就利用adjustUp函数进行向上调整。如下：
void Heap::adjustUp()
{
int curIndex = _heap.size() - 1;
while (curIndex > 0)
{
int parentIndex = (curIndex - 1) / 2;
if (_heap[parentIndex] < _heap[curIndex])
{
std::swap(_heap[parentIndex], _heap[curIndex]);
curIndex = parentIndex;
}
else
{
break;
}
}
}
写一下测试跑跑看吧：
#include "heap.h"
int main() {
Heap heap;
heap.insert(1);
heap.insert(2);
heap.insert(3);
}
喔吼！拿不到数组的值，我们要得到堆顶的值，那就写一个吧：
int Heap::top()
{
if (_heap.size() > 0)
{
return _heap[0];
}
}
运行得到：
可以看到堆顶的数据3，数组下标0处的数据是3，可以我们在插入的时候，0处一开始插入的是1，但是结果是3，这就说明没有问题。
如果要实现topk问题，我们需要每次都将堆顶的元素给删除了，如果求第3大的数，我们就删除两次，然后此时堆顶的元素就是第3大的数了下面我们来实现删除功能：
在数组中如果直接删除下标0处的元素，在进行调整，这样会需要变动整个数组，效率低下；因此，我们选择将下标0处的元素与最后一个元素交换，然后直接删除最后一个元素，在进行向下调整即可：
void Heap::pop()
{
if (_heap.size() > 0)
{
std::swap(_heap[0], _heap[_heap.size() - 1]);
_heap.pop_back();
adjustDown();
}
}
void Heap::adjustDown()
{
int size = _heap.size();
int curIndex = 0, leftIndex = 1;
while (leftIndex < size)
{
if (leftIndex + 1 < size && _heap[leftIndex] < _heap[leftIndex + 1])
{
leftIndex++;
}
if (_heap[curIndex] < _heap[leftIndex])
{
std::swap(_heap[curIndex], _heap[leftIndex]);
curIndex = leftIndex;
leftIndex = curIndex * 2 + 1;
}
else
{
break;
}
}
}
在adjustDown这个函数中，利用leftIndex + 1 < size && _heap[leftIndex] < _heap[leftIndex + 1]来判断左右节点哪一个更大一些，然后用较大值和父节点的值进行比较，如果父节点的值小于子节点的值，那么就要向下调整，也就是需要交换，之后更新当前的父节点和左节点，再次进行判断。
下面进行测试：
结果也没有问题。
然后我们根据这个进行堆排序的编写：
测试代码如下：
int main() {
srand((unsigned int)time(NULL));
std::vector<int> v;
for (int i = 0; i < 100; i++)
{
v.push_back(rand()%100);
}
Heap heap;
heap.sort(v);
for (auto& e : v)
{
std::cout << e << " ";
}
}
结果也没有问题。
完整代码
//heap.h
#pragma once
#include <vector>
#include <iostream>
#include <cassert>
class Heap {
public:
Heap();
~Heap();
void insert(int value);
void adjustUp();
int top();
void pop();
void adjustDown();
void sort(std::vector<int>& v);
private:
std::vector<int> _heap;
};
//heap.cpp
#include "heap.h"
Heap::Heap()
{
}
Heap::~Heap()
{
}
void Heap::insert(int value)
{
_heap.push_back(value);
adjustUp();
}
void Heap::adjustUp()
{
int curIndex = _heap.size() - 1;
while (curIndex > 0)
{
int parentIndex = (curIndex - 1) / 2;
if (_heap[parentIndex] < _heap[curIndex])
{
std::swap(_heap[parentIndex], _heap[curIndex]);
curIndex = parentIndex;
}
else
{
break;
}
}
}
int Heap::top()
{
if (_heap.size() > 0)
{
return _heap[0];
}
}
void Heap::pop()
{
if (_heap.size() > 0)
{
std::swap(_heap[0], _heap[_heap.size() - 1]);
_heap.pop_back();
adjustDown();
}
}
void Heap::adjustDown()
{
int size = _heap.size();
int curIndex = 0, leftIndex = 1;
while (leftIndex < size)
{
if (leftIndex + 1 < size && _heap[leftIndex] < _heap[leftIndex + 1])
{
leftIndex++;
}
if (_heap[curIndex] < _heap[leftIndex])
{
std::swap(_heap[curIndex], _heap[leftIndex]);
curIndex = leftIndex;
leftIndex = curIndex * 2 + 1;
}
else
{
break;
}
}
}
void Heap::sort(std::vector<int>& v)
{
for (int i = 0; i < v.size(); i++)
{
insert(v[i]);
}
for (int i = 0; i < v.size(); i++)
{
v[i] = top();
pop();
}
}
//main.c
#include "heap.h"
#include <ctime>
int main() {
/*Heap heap;
heap.insert(1);
heap.insert(2);
heap.insert(3);
heap.pop();
std::cout << heap.top() << std::endl;
heap.pop();
std::cout << heap.top() << std::endl;*/
srand((unsigned int)time(NULL));
std::vector<int> v;
for (int i = 0; i < 100; i++)
{
v.push_back(rand()%100);
}
Heap heap;
heap.sort(v);
for (auto& e : v)
{
std::cout << e << " ";
}
}
新人创作不易，你的点赞和关注都是对我莫大的鼓励，再次感谢您的观看。