优先队列（堆） 最大堆和最小堆的实现
优先队列
实现的实例：Heap(Binary,Binomial,Fibonacci) 堆
Binary Search Tree 二叉搜索树
小顶堆Mini Heap：优先级越小排在越前面,最小元素永远在堆顶,父亲节点永远比孩子节点的值小。
大顶堆和小顶堆相反
维基百科: https://en.wikipedia.org/wiki/Heap_(data_structure)
堆
堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构，所以堆也叫做二叉堆。
二叉堆满足二个特性
1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。
最大堆和最小堆是堆数据结构的重点。堆排序中使用特别的多。
堆的存储一般是用一个数组实现的，当然也可以用链式存储，但是特别麻烦。
如下我们给出一个数组：
int* Arry={10,16,18,12,11,13,15,17,14,19};
现在我们要根据这个数组来建一个不是真正意义上的堆。
现在的堆并不是真正的堆，它不满足最大堆或者最小堆，所以它是无意义的，我们要调整这个“堆”让它变成最大堆或者最小堆，这一步操作就是调整堆。
调整堆
首先我们要明确调整堆的目的就是让整棵树中的双亲节点都大于孩子节点（这里以最大堆为例）所以我们要从叶子结点开始调整，直到调整到根节点结束，可能调整好这棵树后，子树又不符合最大堆规则，转而调整子树，所以我们把这种方式叫下调（AdjustDown）,下调主要的目的是为了将不符合条件的父节点向下调整
# pragma once
# include<iostream>
# include<vector>
# include<assert.h>
using namespace std;
template<class T>
struct Less
{
bool operator()(const T& l, const T& r)
{
return l < r;
}
};
template<class T>
struct Greater
{
bool operator()(const T& l, const T& r)
{
return l > r;
}
};
template<class T,template<class> class Continer>
class Heap
{
public:
Heap(){};
Heap(const T* a,size_t size,Continer<T> con=Greater<T>());
Heap(const vector<T> &v);
void Push(const T&x);
T Pop();
T &GetTop(){return _a.back();}
bool Empty(){return _a.empty();}
vector<T> getArray(){return _a;}
size_t size(){return _a.size();}
vector<T> sort();
protected:
void _AdjustDown(size_t parent,size_t size); //下调
void _AdjustUp(size_t child); //上调
protected:
vector<T> _a;
Continer<T> _con;
};
template<class T, template<class> class Continer>
Heap<T,Continer>::Heap(const T* a,size_t size ,Continer<T> con)
{
_a.reserve(size);
for (size_t i = 0; i < size; ++i)
{
_a.push_back(a[i]);
}
//建堆
for (int i = (_a.size() - 2) / 2; i >= 0; i--) //记住 i=(a.size()-2)/2这个公式
//从第一个非叶子结点开始下调，叶子结点可以看作是一个大堆或小堆
{
_AdjustDown(i);
}
}
template<class T, template<class> class Continer >
void Heap<T,Continer>::_AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
size_t size = _a.size();
while (child < size) //避免数组访问越界
{ //遍历子树
if (child + 1 < size&&_con(_a[child+1],_a[child]))
//比较左右孩子 第一个判断是否存在右孩子 第二个比较左右孩子
++child;
if (_con(_a[child],_a[parent]))
{
swap(_a[parent], _a[child]); //交换父子节点
parent = child; //接下来将孩子节点的位置作为父亲节点,比较孩子节点下面的子树
child = parent * 2 + 1; //公式
}
else
break;
}
}
在这里是使用的类去封装堆结构，并且用了仿函数的方式去复用最大堆和最小堆的代码。在这里默认把堆调整为最大堆。
以下是堆的调用：
int array[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
size_t size = sizeof(array) / sizeof(int);
Heap<int,Greater> h(array, size, Greater<int>());//因为默认为大顶堆，所以可以省略Greater
我们的调整堆的操作是从二叉树的第一个非叶子结点开始调整。有的读者会问为什么不从最后一个结点调整呢？因为所有叶子结点我们都可以看作一个最大堆或者最小堆，我们完全不需要去调整。
要调整为一个最小堆的话只要修改一下调用即可：
int array[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
size_t size = sizeof(array) / sizeof(int);
Heap<int，Less> h1(array, size, Less<int>());
插入数据
Push操作：向堆中插入一个数据，也就是往数组中插入一个数据，插入数据以后一般都不是最大堆（最小堆），我们得去调整。
上调（AdjustUP）：把新插入的结点大于（小于）双亲节点则往上调，直到满足最大堆（最小堆）。
template<class T, template<class> class Continer>
void Heap<T, Continer>::Push(const T& x)
{
_a.push_back(x);
_AdjustUp(_a.size() - 1);
}
template<class T, template<class> class Continer >
void Heap<T, Continer>::_AdjustUp(size_t child) //上调
{
size_t parent = (child - 1) / 2; //获取数组中父亲节点的位置
while (child > 0)
{
if (_con(_a[child] , _a[parent]))
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}删除最大堆（最小堆）中的根结点
我们把根节点删除以后剩下的结点就不构成一棵树结构了，所以我们可以换一种思路让堆保持原来的结构。
方法就是把根节点和最后一个结点交换，删除最后一个结点，这样就不会破环结构了。
把结点删除后，堆肯定不满足最大堆（最小堆）了，所以我们还要调整堆。这次我们要从根节点往叶子结点调，这样很快，因为原来的堆根节点的左右子树都已经满足大小堆了。利用下调来调整：
template<class T, template<class> class Continer >
void Heap<T, Continer>::Pop()
{
assert(!_a.empty());
size_t size = _a.size();
swap(_a[0], _a[size - 1]);
_a.pop_back();
_AdjustDown(0);
}
排序输出
固定一个最大值，将剩余的数用下调再构造成一个大根堆（元素下降），直到剩余元素为空的时候，数组排序结束。
template<class T,template<class> class Continer>
vector<T> Heap<T,Continer>::sort()
{
for(int i=size()-1;i>0;i--)
//i一定要是size()-1.因为需要的排序的数组大小为未排序的数组大小(最后一个已经排好序了)
{
swap(_a[0],_a[i]);
_AdjustDown(0,i);
}
return _a;
}测试代码
/*************************************************************************
> File Name: main.cpp
> Author: 堆排序
> Mail:
> Created Time: 2020年01月02日 星期四 12时01分02秒
************************************************************************/
# include<iostream>
# include <algorithm>
# include <assert.h>
# include <vector>
using namespace std;
template<class T>
struct less{
bool operator()(const T &l,const T &r)
{
return l<r;
}
};
template<class T>
struct Greater{
bool operator()(const T &l,const T &r)
{
return l>r;
}
};
template<class T,template<class> class Continer>
class Heap
{
public:
Heap(){};
Heap(const T* a,size_t size,Continer<T> con=Greater<T>());
Heap(const vector<T> &v);
void Push(const T&x);
T Pop();
T &GetTop(){return _a.back();}
bool Empty(){return _a.empty();}
vector<T> getArray(){return _a;}
size_t size(){return _a.size();}
vector<T> sort();
protected:
void _AdjustDown(size_t parent,size_t size);
void _AdjustUp(size_t child);
protected:
vector<T> _a;
Continer<T> _con;
};
template<class T,template<class> class Continer>
Heap<T,Continer>::Heap(const T * a,size_t size,Continer<T> con)
{
_a.reserve(size);
for(size_t i=0;i<size;i++)
{
_a.push_back(a[i]);
}
for(int i=(_a.size()-2)/2;i>=0;i--)
{
_AdjustDown(i,size);
}
}
template<class T,template<class> class Continer>
void Heap<T,Continer>::_AdjustDown(size_t parent,size_t size)
{
size_t child=parent * 2+1;
while(child<size)
{
if(child+1<size&& _con(_a[child+1],_a[child]))
{
++child;
}
if(_con(_a[child],_a[parent]))
{
swap(_a[parent],_a[child]);
parent=child;
child=parent *2 +1;
}else
break;
}
}
template <class T,template<class> class Continer>
void Heap<T,Continer>::Push(const T & x)
{
_a.push_back(x);
_AdjustUp(_a.size()-1);
}
template <class T,template<class> class Continer>
void Heap<T,Continer>::_AdjustUp(size_t child)
{
size_t parent=(child -1)/2;
while(child>0)
{
if(_con(_a[child],_a[parent]))
{
swap(_a[child],_a[parent]);
child=parent;
parent=(child-1)/2;
}else{
break;
}
}
}
template<class T,template<class> class Continer>
T Heap<T,Continer>::Pop()
{
T temp;
assert(!_a.empty());
size_t size=_a.size();
swap(_a[0],_a[size-1]);
temp=_a.back();
_a.pop_back();
_AdjustDown(0,size);
return temp;
}
template<class T,template<class> class Continer>
vector<T> Heap<T,Continer>::sort()
{
for(int i=size()-1;i>0;i--)
{
swap(_a[0],_a[i]);
_AdjustDown(0,i);
}
return _a;
}
int main()
{
int array[]={10,16,18,12,11,13,15,17,14,19};
Heap<int,Greater> h(array,sizeof(array)/sizeof(int));
cout<<"大顶堆"<<endl;
vector<int> v1=h.getArray();
for_each(v1.begin(),v1.end(),[](int val){cout<<val<<" ";});
cout<<endl;
cout<<"排序后的数组"<<endl;
vector<int> v=h.sort();
for_each(v.begin(),v.end(),[](int val){cout<<val<<" ";});
cout<<endl;
}
![堆排序.jpg][3]
总结
堆和栈是计算机内存最常用的结构。
有了最大堆和最小堆，我们可以利用他们的特性来实现堆排序。
数组构建堆最重要的还是将数组下标转换为对应的父节、子节点。最后一个有叶子节点的父节点的下标为(size-2)/2
大部分转载自https://blog.51cto.com/helloleex/1768758 稻草阳光L
