Heapsort

Heapsort is a sorting algorithm that that take advantage of the characteristics of #202202071755.

Detail

• If the heap is intended to be reused, place the element deleted to the end of the heap.

Analysis

• It will result in \(O(N \log N)\) at worst since DeleteMin is performed on N elements.

Attention

• If the heap is not reused, the space complexity could be \(O(N)\) which is inefficient.
• The alternative to move the elements in Heapsort is to use Floyd’s algorithm

Implementation

Note: The above algorithm is using DeleteMax.

#define LeftChild(i) (2 * (i) + 1)

void PercDown(ElementType A[], int i, int N) {
  int Child;
  ElementType Tmp;

  for (Tmp = A[i]; LeftChild(i) < N; i = Child) {
    Child = LeftChild(i);
    if (Child != N - 1 && A[Child + 1] > A[Child])
      Child++;
    if (Tmp < A[Child])
      A[i] = A[Child];
    else
      break;
  }
  A[i] = Tmp;
}

void Heapsort(ElementType A[], int N) {
  for (int i = N / 2; i >= 0; i--)    // BuildHeap
    PercDown(A, i, N);
  for (int i = N - 1; i > 0; i--) {
    Swap(&A[0], &A[i]);               // DeleteMax
    PerDown(A, 0, i);
  }
}