#include <stdio.h>

void sift(int a[], int i, int n)/* i为根节点,n为节点总数 */
{
  int child, tmp;

  for (tmp = a[i]; n > 2 * i; i = child)
  {
    child = 2 * i;     /* i的左孩子为2*i,右孩子为2*i+1 */
    if ((child != n-1) && (a[child+1] > a[child]))     /* 让child指向孩子中较大的一个 */
    {
      child++;
    }
    if (tmp < a[child])/* 如果孩子节点大 */
    {
      a[i] = a[child];/* 交换孩子节点和根节点 */
    }
    else
      break;
  }
  a[i] = tmp;    /* 将根放在合适位置 */
}

void heapsort(int a[],int n)/* 对a[1...n]进行排序 */
{
  int i, tmp;

  for (i = n / 2; i >= 0; i--)/* 建立初始堆 */
  {
    sift(a, i, n);
  }

  for (i = n - 1; i > 0; i--)/* 进行n-1趟排序 */
  {
    tmp = a[0];      /* 交换堆顶元素和最后一个元素 */
    a[0] = a[i];
    a[i] = tmp;
    sift(a, 0, i);    /* 将a[1..n-1]重建为堆 */
  }
}


int main(int argc, char* argv[])
{
  int a[7] = {8,9,3,5,1,6,4};
  int i;

  heapsort(a, 7);

  for (i = 0; i < 7; i++)
    printf("%d  \n", a[i]);


  return 0;
}

#include <stdio.h>

#define PARENT(i)  i >> 1
#define LEFT(i)    i << 1
#define RIGHT(i)   (i << 1) + 1
#define HeapBase   1
long HeapSize = 0;

void Exchange(long* a, long* b)
{
        long t = 0;
        t = *a;
        *a = *b;
        *b = t;
}

void MaxHeapify(long* Ary, long i)
{
        long l = LEFT(i);
        long r = RIGHT(i);
        long largest = 0;

        if (l <= HeapSize)
        {
                if (*(Ary + l) > *(Ary + i))
                        largest = l;
                else
                        largest = i;
        }
        if (r <= HeapSize)
                if (*(Ary + r) > *(Ary + largest)) largest = r;
        if ((largest != i) && (largest >= HeapBase) && (largest <= HeapSize))
        {
                Exchange(Ary + i, Ary + largest);
                MaxHeapify(Ary, largest);
        }
}

void BuildMaxHeap(long* Ary)
{
        long i = 0;
        for (i = HeapSize / 2; i >= HeapBase; i--)
        {
                MaxHeapify(Ary, i);
        }
}

//Ary[1..n]
void HeapSort(long* Ary, long dwSize)
{
        long i = 0;
        HeapSize = dwSize;
        BuildMaxHeap(Ary);
        for (i = dwSize; i >= HeapBase; i--)
        {
                Exchange(Ary + HeapBase, Ary + i);
                HeapSize--;
                MaxHeapify(Ary, HeapBase);
        }
}

int main()
{
        long a[4] = {0};
        a[1] = 2;
        a[2] = 1;
        a[3] = 8;
        HeapSort(a, 3);
        printf("%ld\n", a[1]);
        printf("%ld\n", a[2]);
        printf("%ld\n", a[3]);
        return 0;
}