堆的创建
堆其实是一种完全二叉树，堆分为大堆和小堆，当满足Key[i]>Key[2i+1]以及Key[i]>Key[2i+2]时是大堆，当满足Key[i]<Key[2i+1]以及Key[i]<Key[2i+2]时是小堆。
计算
安全
数据库
网络和加速
企业服务
#pragma once
#include<vector>
#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
class Heap
{
public:
Heap()
:_a(NULL)
{}
Heap(const T* a,size_t size)
{
assert(a);
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);
}
}
void Push(const T& x)
{
_a.push_back(x);
_AjustUp(_a.size()-1);
}
void Pop()
{
assert(_a.empty());
swap(_a[0],_a[a.size()-1]);
_AdjustDown();
}
protected:
void _AdjustDown(size_t parent)
{
size_t child = parent*2+1;
while(child > 0)
{
if(_a[child] < _a[child+1] && child<_a.size())
{
++child;//如果左孩子比有孩子大的话，不做处理，反之，使得大的变成child = child+1;
}
if(_a[child]>_a[parent]) //每次交再向下调整
{
swap(_a[child],_a[parent]);
parent = child;
child = parent*2+1;
}
else
{
break;
}
}
}
void _AjustUp(size_t child)
{
int parent = (child-1)/2;
while(child > 0) //这里必须判断孩子下标，否则很危险。如果要用父亲的判断，则应该把size_t改为int
{
if(_a[parent]<_a[child])
{
swap(_a[parent],_a[child]);
child = parent;
parent = (child-1)/2;
}
else
{
break;
}
}
}
protected:
vector<T> _a;
};
void TestHeap()
{
int a[] = {10,11,13,12,16,18,15,17,14,19};
Heap<int> Hp1(a,sizeof(a)/sizeof(a[0]));
Hp1.Push(20);
}
int main()
{
TestHeap();
system( "pause");
return 0;
}2.堆排序思想
利用大根堆小根堆堆顶元素是最大记录（最小记录），使得每次从无序中选择最大（最小记录）就变得简单了。这里采用大根堆思想，
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最 后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排 序过程完成。
//堆排序
#include<iostream>
#include<assert.h>
using namespace std;
void AjustDown(int a[],size_t n,int parent)
{
assert(a);
int child = parent*2+1;
while(child<n)
{
if(child<n &&(a[child]<a[child+1]))
{
++child;
}
if(a[child]>a[parent])
{
swap(a[child],a[parent]);
parent = child;
}
else
{
break;
}
}
}
void HeapSort(int a[],size_t n)
{
assert(a);
for(int i=(n-2)/2;i>0;--i)
{
AjustDown(a,n,i);
}
for(int i = 0; i < n; ++i)
{
swap(a[0],a[n-i-1]);
AjustDown(a,n-i-1,0);
}
}
void Test()
{
int a[]={2,1,4,3,5,6,0,4,7,8,9};
HeapSort(a,sizeof(a)/sizeof(a[0]));
}
int main()
{
Test();
system("pause");
return 0;
}算法分析：
从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1...n]中选择最大记录，需比较n-1次，然后 从R[1...n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的 特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为 nlogn。堆排序为不稳定排序，不适合记录较少的排序。
3.堆的应用
例：100W个数中找出最大的100个
1 小根堆；
2 堆固定大小为100；
3 堆元素个数小于100时直接加入堆；
4 堆元素个数等于100时，与堆顶元素比较，比堆顶元素大的进堆，并调整堆；
5 遍历结束时，堆中元素为100个最大数。
#pragma once
#include<iostream>
#include<assert.h>
#include<time.h>
#include<stdlib.h>
using namespace std;
const int N = 10000;
const int K = 100;
void _AjustDown(int TopK[],int size,int parent)
{
assert(TopK);
int child = parent*2+1;
while( child < size)
{
if(child < size && (TopK[child] < TopK[child+1]))
{
++child;
}
if(TopK[child] > TopK[parent])
{
swap(TopK[child],TopK[parent]);
parent = child;
}
else
{
break;
}
}
}
void GetTop(int a[])
{
assert(K < N);
int TopK[K];
for(int i=0;i<K;++i)
{
TopK[i] = a[i];
}
//建堆
for(int i = (K-2)/2;i>= 0;--i)
{
_AjustDown(TopK,K,0);
}
for(int i=0;i<K;++i)
{
cout<<TopK[i]<<" ";
}
}
void TestTopK()
{
srand(time(0));
int a[N];
int TopK[K];
for(int i= 0;i<N;++i)
{
a[i] = rand()%10000;
}
for(int i = N-K;i<N;++i)
{
a[i] = 10000+i;
}
GetTop(a);
}
int main()
{
TestTopK();
system("pause");
return 0;
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
