今天开始学算法系列--堆概念及堆排序的实现

    今天的主角-----堆

    很多情况下，大家可能会有这么一个想法，给我一串数据，但是，我只focus当前这串数据的最大值或最小值，也就是说，我只想取出这串数据的最大值或最小值，而后续的数我并不关心。而在取出一个数之后，我对这串剩下的数据在进行取数操作，也是只关心当前数据中的最大或最小值，后续的数据如何排列也漠不关心。对于这类问题，堆就提供了一个良好的解决方案。  这时候如果你稍微动动脑子，也就能明白什么是推排序了吧   没错！ 每次从这串数据中拿出的都是当前最大的数，自然当你全都拿出来后，数据也自然排列好了！  真实个不错的算法，那我们就先来看看堆的概念吧！

    

   堆其实是一颗2叉树，注意，它仅仅是棵二叉树，并没有一定的顺序排列，化而言之，其实你就直接可以把一个数组按照树的逐层遍历来构造这么一颗2叉树（什么叫逐层呢？ 其实就是将一个二叉树从上往下，从左往右依次铺开 如下图）

  

这种逐层安排出来的二叉树有什么特点呢？ 仔细看就能发现，一个数组有6个元素，6/2=3，看下，是不是只有0,1,2这三个元素在这颗树上才有子节点呢？没错吧，这样对于我们后续的排序大小堆是很有帮助的!

接着看，还有一个很重要的性质就是，假设每个父节点在数组中的位置是i，每个父节点的子节点必定是i*2+1（左节点），i*2+2（右节点），这真是很有用的性质，方便了我们排序大小堆。

   好了有了这两个性质，我们来看下怎么来进行大堆排序吧（小堆的做法相仿）

   大堆的排序是部分排序，即只要关注每个子节点和父节点直接的大小关系就可以了（见下图）

   

从上图可以看出，其实就是从父子节点中找出最大的那个数然后放在父节点的位置，这样几次过后，堆顶一定是存放最大的数。这样一来大堆就实现了！很简单吧！

  那堆排序又是如何进行的呢？其实跟简单，就是讲堆顶元素取走，然后用堆尾元素将其替换（堆尾元素其实就是堆的右下方的元素），之后再对该堆进行大堆规范的排列调整 （见下图）

  

这样重复取出，最终自然就能得到一个从大到小的排序序列了

   好了概念讲完了，最后还是上实现代码，什么都不如代码来的方便，一目了然！！！！！

    

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;
int data[13]={13,7,2,9,6,4,15,17,18,45,1,10,16};

struct node{
    int num;
    struct node *left;
    struct node *right;
};
typedef struct node node_t;

node_t *topHeap = NULL;

void createBigHeap(int num)
{
    int size = num;
    int i = size / 2;   //为什么要把数组的总数除以2呢？ 你会发现，其实只有这些数才会有子节点
    int j = i - 1;
    //下这个for循环主要就是进行大堆的排序
    for(;j >= 0;j--)
    {
        if((j*2+1)<size && data[j]<data[j*2+1])
        {
            if((j*2+2)<size && data[(j*2+1)] < data[(j*2+2)])
            {
                int tmp = data[j*2+2];
                data[j*2+2] = data[j];
                data[j] = tmp;
            }
            else{
                int tmp = data[j*2+1];
                data[j*2+1] = data[j];
                data[j] = tmp;
            }
        }
        else if((j*2+1)<size && data[j]>data[j*2+1])
        {
            if((j*2+2)<size && data[j] < data[(j*2+2)])
            {
                int tmp = data[j*2+2];
                data[j*2+2] = data[j];
                data[j] = tmp;
            }
        }
    }
}

void sortHeap(int num)
{
    vector<int> sortdata;
    int i = num - 1;
    int j = 0;
    //以下这个for循环就是将堆内最后的元素和堆顶元素进行互换，并且移除堆顶元素
    for(;i>0;i--)
    {
        sortdata.push_back(data[j]);
        data[j] = data[i];
        num--;
        createBigHeap(num);
    }
    sortdata.push_back(data[j]);
    vector<int>::iterator itr;
    for(itr = sortdata.begin();itr != sortdata.end();itr++)
    {
        cout<<*itr<<endl;
    }
}

int main()
{
    int num = sizeof(data) / 4;
    createBigHeap(num);
    sortHeap(num);
}

好了 今天就讲到这了