堆排序

//这里构建数组过程只是做一个简单的示例，复杂情况暂不考虑
//接受键盘输入n个数，构建数组
int *setUpArr()
{
    int n;
    scanf("%d",&n);
    int *arr = (int *)malloc(sizeof(int)*n);

    if(arr)
    {
            for(int i = 0; i < n; i++)
        {
        scanf("%d",&arr[i]);
        }
            return arr;
    } 
    return NULL;
}

//建堆的过程是从最后一个非叶子节点开始调整
int initHeap(int *arr) {

    if(arr == NULL)
      return 0;
    
    int n = sizeof(arr);
    
    //从最后一个非叶子节点开始进行倒序遍历，遍历每一个非叶子节点，一次进行向下调整
    for(int i = (n-1)/2;i>=0;i--)
    {
        int parent = i;
        //父节点parent左孩子的下标
        int child = 2*parent + 1;
        
        /*
          如果左孩子的下标在数组容纳范围内，那么就应该进行父子节点的比较
          也就是说只要有孩子节点，那么这个父节点就可能需要进行调整
        */
        while(child <= n-1)
        {
            //下面使用 child 保存左右孩子节点中较小的节点下标
            //判断是否存在右孩子节点，并且判断如果存在是否比左孩子大
            if(child+1<n && arr[child]>arr[child+1])
            {
                //右孩子节点存在并且比左孩子大，那么child保存右孩子节点
                child ++;
            }
            //左右孩子节点中较小的节点 child 跟父节点 parent 进行比较
            if(arr[child] < arr[parent])
            {
                //如果 child 节点比父节点 parent 小，那么进行交换
                int x = arr[child];
                arr[child] = arr[parent];
                arr[parent] = arr[child];
                //交换后将父节点下标 parent 改为进行了替换的最小节点的下标 child
                parent = child;
                /* 
                    将 child 改为当前父节点 parent 的左孩子节点，进行下一轮调整
                    因为只要某一个孩子节点跟父节点进行了交换调整
                    那么以该孩子节点为父节点的树就可能需要进行调整
                */
                child = 2*child+1;
            }
            else
            {
                /*
                    因为这里是从最后一个非叶子节点倒序进行调整的
                    所以只要当前的父子节点已经是小堆形式，那么就不需要再对下面的子树进行调整了
                */
                break;
            }
        }
    }
    return 1;
} 

void heapSort(int *arr)
{
    if(arr == NULL)
      return 0;
    
    int maxIndex = sizeof(arr) - 1;
    
    /*
        这里可以改为
        for (int maxIndex = sizeof(arr) - 1; maxIndex >=1; maxIndex --) 
        可以这样理解：每次排序确定一个元素的位置，将它放在参与排序的数组元素末尾
    */
    while(maxIndex > 0)
    {
         int x = arr[0];
         arr[0] = arr[maxIndex];
         arr[maxIndex] = x;

         /*
          如果使用for循环，这一行应该改为int sortingArrlastIndex= maxIndex - 1;
          下面的maxIndex都替换为sortArrlastIndex
        */
         maxIndex-- ;
        
         int parent = 0;
         int child = 2*parent +1;

          /*
            有交换则以被交换的孩子节点为根的树可能需要继续进行调整，那么就要继续
            如果没有交换那么就可以直接跳出while循环，此时已经将当前堆调整完毕
         */
         //如果使用for循环，这里maxIndex应该替换为sortingArrlastIndex
         while(child <= maxIndex)
          {
              //如果使用for循环，这里maxIndex应该替换为sortingArrlastIndex
              if(child+1<=maxIndex && arr[child]>arr[child+1])
              {
                  child ++;
              }
              if(arr[child]<arr[parent])
              {
                  int tmp = arr[child];
                  arr[child] = arr[parent];
                  arr[parent] = tmp;
                  /*
                    有交换则以被交换的孩子节点为根的树可能需要继续进行调整，
                    因此将 parent 改为当前被替换了的孩子节点，然后将 child 改为
                    以 parent 为父节点的左孩子节点继续进行调整
                  */
                  parent = child;
                  child = 2*parent + 1;
              }
              else
              {
                  break;
              }
          }
    }
}

void fixupHeap(int *arr)
{
         int maxIndex = sizeof(arr) - 1;
         int parent = 0;
         int child = 2*parent +1;

          /*
            有交换则以被交换的孩子节点为根的树可能需要继续进行调整，那么就要继续
            如果没有交换那么就可以直接跳出while循环，此时已经将当前堆调整完毕
         */
         while(child <= maxIndex)
          {
              if(child+1<=maxIndex && arr[child]>arr[child+1])
              {
                  child ++;
              }
              if(arr[child]<arr[parent])
              {
                  int tmp = arr[child];
                  arr[child] = arr[parent];
                  arr[parent] = tmp;
                  /*
                    有交换则以被交换的孩子节点为根的树可能需要继续进行调整，
                    因此将 parent 改为当前被替换了的孩子节点，然后将 child 改为
                    以 parent 为父节点的左孩子节点继续进行调整
                  */
                  parent = child;
                  child = 2*parent + 1;
              }
              else
              {
                  break;
              }
          }
}

堆排序时间复杂度

堆排序的时间复杂度，主要在初始化堆过程和每次选取最大数后重新建堆的过程；

初始化建堆过程时间：O(n)

推算过程：
首先要理解怎么计算这个堆化过程所消耗的时间，可以直接画图去理解；
假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；
那么总的时间计算为：

s = 2^( i - 1 ) * ( k - i )；

其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；

S = 2^(k-2) * 1 + 2^{(k-3)*2.....+2*(k-2)+2}(0)*(k-1) ===> 因为叶子层不用交换，所以 i 从 k-1 开始到 1；

这个等式求解，我想高中已经会了：等式左右乘上2，然后和原来的等式相减，就变成了：

S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ..... + 2 - (k-1)

除最后一项外，就是一个等比数列了，直接用求和公式：S = {a1[ 1- (q^n) ] } / (1-q)；

S = 2^k -k -1；

又因为k为完全二叉树的深度，所以

(2^k) <= n < (2^k -1 )

总之可以认为：k = logn （实际计算得到应该是 log(n+1) < k <= logn ）;

综上所述得到：S = n - longn -1，所以时间复杂度为：O(n)

更改堆元素后重建堆时间：O(nlogn)

推算过程：
循环 n -1 次，每次都是从根节点往下循环查找，所以每一次时间是 logn，总时间：

logn(n-1) = nlogn - logn ；

综上所述：建堆的时间复杂度是O(n)(调用一次);调整堆的时间复杂度是lgn,调用了n-1次,所以堆排序的时间复杂度是O(n)+O(nlgn) ~ O(nlgn)。

算法设计：从一个很大很大的数组里找前N个最大（小）数的思路之一
http://blog.csdn.net/yanzi1225627/article/details/8109035