堆的创建&堆排序&堆的应用-创新互联

1. 堆的创建

   

   成都创新互联公司专注于企业成都全网营销推广、网站重做改版、元宝山网站定制设计、自适应品牌网站建设、H5页面制作、电子商务商城网站建设、集团公司官网建设、成都外贸网站建设公司、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为元宝山等各大城市提供网站开发制作服务。

堆其实是一种完全二叉树，堆分为大堆和小堆，当满足Key[i]>Key[2i+1]以及Key[i]>Key[2i+2]时是大堆，当满足Key[i]

#pragma once
#include
#include
#include
using namespace std;
template
class Heap
{
public:
    Heap()
        :_a(NULL)
    {}

    Heap(const T* a,size_t size)
    {
        assert(a);
        for(size_t i=0;i0;--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 _a;
};
void TestHeap()
{
    int a[] = {10,11,13,12,16,18,15,17,14,19};
    Heap 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
#include
using namespace std;
void AjustDown(int a[],size_t n,int parent)
{
    assert(a);
    int child = parent*2+1;
    while(childa[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
#include
#include
#include
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= 0;--i)
    {
        _AjustDown(TopK,K,0);
    }
    for(int i=0;i
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
            

            当前文章：堆的创建&堆排序&堆的应用-创新互联            

            分享链接：http://cqcxhl.cn/article/ccsesh.html