排序-堆排序

堆排序：
堆排序分为三个步骤：
1.HEAPIFY(堆化，将指定的数据区调整成一个堆）
2.BUILD_HEAP(建堆,将整块数据建成一个堆)
3.HEAPSORT(排序，调整堆)
伪码：

Heapify (A, i)

1. l ← left [i]
2. r ← right [i]
3. if l ≤ heap-size [A] and A[l] > A[i]
4.     then largest ← l
5.     else largest ← i
6. if r ≤ heap-size [A] and A[i] > A[largest]
7.     then largest ← r
8. if largest  ≠ i
9.     then exchange A[i] ↔ A[largest]
10.         Heapify (A, largest)

BUILD_HEAP (A)

1. heap-size (A) ← length [A]
2. For i ←  floor(length[A]/2) down to 1 do
3.         Heapify (A, i)

HEAPSORT (A)

1. BUILD_HEAP (A)
2. for i ← length (A) down to 2 do
   exchange A[1] ↔ A[i]
   heap-size [A] ← heap-size [A] - 1
   Heapify (A, 1)

void heapSort(int numbers[], int array_size)
    {
      int i, temp;

      for (i = (array_size / 2)-1; i >= 0; i--)
        siftDown(numbers, i, array_size);

      for (i = array_size-1; i >= 1; i--)
      {
        temp = numbers[0];
        numbers[0] = numbers[i];
        numbers[i] = temp;
        siftDown(numbers, 0, i-1);
      }
    }


    void siftDown(int numbers[], int root, int bottom)
    {
      int done, maxChild, temp;

      done = 0;
      while ((root*2 <= bottom) && (!done))
      {
        if (root*2 == bottom)
          maxChild = root * 2;
        else if (numbers[root * 2] > numbers[root * 2 + 1])
          maxChild = root * 2;
        else
          maxChild = root * 2 + 1;

        if (numbers[root] < numbers[maxChild])
        {
          temp = numbers[root];
          numbers[root] = numbers[maxChild];
          numbers[maxChild] = temp;
          root = maxChild;
        }
        else
          done = 1;
      }
    }