数据结构::堆

堆的定义及解释

专业定义：

如果有一个关键码的集合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和emptysize_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;}
};