堆的定义：
堆是一种特别的二叉树，满足以下条件的二叉树，可以称之为堆：
1、完全二叉树；2、每一个节点的值都必须大于等于或者小于等于其孩子节点的值。
堆的特点：1、可以再O(logN)的时间复杂度向堆中插入元素；2、可以在O(logN)的时间复杂度向堆中删除元素；3、可以在O(1)的时间复杂度内获取堆中的最大值或最小值。
最大堆：堆中每一个节点的值都大于等于 孩子节点的值。最小堆：堆中每一个节点的值都小于等于其孩子节点的值。
堆的插入过程：插入操作是指向堆中插入一个元素。元素插入之后，堆依旧需要维持它的特性。
流程：向堆尾插入新的元素，自底向上进行冒泡操作。
堆的删除过程：删除操作是指在 堆 中删除堆顶元素。元素删除之后，堆 依旧需要维持它的特性。
流程：将堆底元素移动至堆顶，逆向进行冒泡操作。
堆的代码实现：
#include<iostream>
#include<vector>
#include<string.h>
#include<utility>
using namespace std;
template<class T>
class Heap{
public:
Heap()
{}
Heap(const T* array,size_t size)
{
v.resize(size);
for (size_t i = 0; i < size; ++i){
v[i] = array[i];
}
_CreateHeap();
}
//插入元素
void Push(size_t data)
{
v.push_back(data);
if (v.size() < 2)
return;
_AdjustUp(v.size()-1);
}
//删除元素
void Pop()
{
if (v.empty())
return;
size_t last = v.size() - 1;
swap(v[last], v[0]);
v.pop_back();
_AdjustDown(0);
}
//判断堆是否为空
bool Empty()const
{
return v.empty();
}
//求堆的大小
size_t Size()const
{
return v.size();
}
//取堆顶层元素
T Top()
{
return v[0];
}
private:
//实现最小堆
void _CreateHeap()
{
if (v.size() <= 1)
return;
int root = (v.size() - 1 - 1) >> 1;
for (; root >= 0;root--){
_AdjustDown(root);
}
}
//向下调整
void _AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
size_t size = v.size();
while (child<size){
if (child + 1 < size&&v[child] > v[child + 1])
child += 1;
if (v[parent] > v[child]){
swap(v[parent], v[child]);
parent = child;
child = parent * 2 + 1;
}
else{
return;
}
}
}
//向上调整
void _AdjustUp(size_t child)
{
size_t parent = (child - 1) >> 1;
while (0!=child){
if (v[parent] > v[child]){
swap(v[parent], v[child]);
child = parent;
parent = (child - 1) >> 1;
}
else
return;
}
}
private:
vector<T> v;
};
void test(){
int arr[] = { 53, 17, 78, 9, 45, 65, 87, 23 };
Heap<int> h(arr, sizeof(arr) / sizeof(arr[0]));
h.Push(5);
h.Size();
h.Pop();
h.Size();
h.Top();
}
int main(){
test();
return 0;
}堆的时间复杂度
| 「堆」的用法 | 时间复杂度 | 空间复杂度 |
| 创建「堆」 | O(N) | O(N) |
| 插入元素 | O(logN) | O(1) |
| 获取堆顶元素 | O(1) | O(1) |
| 删除堆顶元素 | O(logN) | O(1) |
| 获取「堆」的长度 | O(1) | O(1) |
堆排序算法步骤如下：
1、将所有元素堆化成一个堆
2、取出并删除堆顶元素，并将其放置在存储有序的数据集中
3、对堆进行调整
4、重复2与3，直到堆中没有元素
时间复杂度：O(NlogN)。N是堆中的元素个数
空间复杂度：O(N)