堆排序（C语言实现）迭代

首先分清二叉树和堆的区别

堆可以被定义为一棵二叉树，树的节点中包含键（每个节点一个键），并且满足下面两个条件：
（1）树的形状：简称为完全二叉树，这意味着，树的每一层都是满的，除了最后一层最右边的元素可能缺位。
（2）父母优势：堆特性（heap property）每一个节点的键值都要大于或者等于它子女的键（对于任何叶子我们认为这个条件都是自动满足的）

只存在一棵N个节点的完全二叉树。它的高度等于（log2n)向下取整
堆的根总是包含了堆的最大元素

用数组来实现堆，其中：父母节点的键将会位于数组的前（n/2)向下取整位置中，而叶子的节点的键将会占据后n/2向上取整的位置中
在数组中，对于一个位于父母位置i的键来说，它的子女将会位于2i和2i+1中的元素，相反则是i位置的键来说，父母会位于i/2向下取整

在堆排序中最核心的步骤则是“堆化”
有两种方法：自底向上堆构造，在初始化一棵包含N个节点的完全二叉树时，按照给定的顺序来放置键，从最后的父母节点开始，到根为止，该算法检查这些节点的键是否满足父母优势要求。如果该节点不满足，该算法把节点的键K和它子女的最大键进行交换，然后再检查在新位置上，K是不是满足父母优势要求，这个过程一直继续到对K的父母优势要求满足为止

在堆排序之后从堆中删除最大的键：
根的键和堆的最后一个键K做交换
堆的规模减一，即最后元素即为最大元素
继续堆化

此外，还有自顶向下构造

迭代：注意数组下标是从0开始的，当下标为0时，2*0依旧是0是无法判断其子女的，所有应该从1开始，元素下标对应-1就可以。

//堆排序
#include<stdio.h>
#include<stdlib.h>
void heap(int h[],int n);
//最后消除重复变量定义以及无用头文件
int main()
{
    int n,i;
    int *h=NULL;
    FILE *fp=stdout;
    freopen("filein.txt","r",stdin);
    freopen("out.txt","w",stdout);
    scanf("%d",&n);
    h=(int *)malloc(n*sizeof(int));


    for(i=0;i<n;i++)
    {
        scanf("%d",&h[i]);
    }
    ///假设现在数组从1开始

    for(i=n;i>1;i--)
    {
        heap(h,i);
        int temp=h[0];
        h[0]=h[i-1];//n he iiiiiiiiiiiiiiii
        h[i-1]=temp;
    }
    for(i=0;i<n;i++)
    {
        printf("%d ",h[i]);
    }
    free(h);
    return 0;
}
void heap(int h[],int n)
{
    int k,v,j;
    bool heap;
    for(int i=n/2;i>0;i--)
    {
        k=i;
        v=h[k-1];
        heap=false;
        while(!heap && 2*k<=n)
        {
            j=2*k;
            if(j<n)//有两个子女
            { if(h[j-1]<h[j]) j+=1;}
            if(v>=h[j-1]) {heap=true;}
            else{ h[k-1]=h[j-1]; k=j;}
            h[k-1]=v;

        }
    }
}