Heap Sort

Sorting Method

 

  • Read This PDF (http://www.cse.uconn.edu/~ykim/cse259/LC/heapsort.pdf)
  • Heapsort(A)
        Build-Max-Heap(A)
        for i = length(A) downto 2
              exchange A[1] = A[i]
              heap-size[A] = heap-size[A]-1
              Max-Heapify(A, 1)
  • Max-Heapify(A, i):
  • The subtree rooted at i becomes a max-heap
  • Build-Max-Heap(A):
  •     for i = heapsize[A]/2 downto 1
              Max-Heapify(A, i)

Source Code

void Max_Heapify(int numbers[], int root, int bottom);

void heapSort(int numbers[], int array_size)
{
  int i, temp;
  //BUILD_MAX_HEAP
  for (i = (array_size / 2)-1; i >= 0; i--)
    Max_Heapify(numbers, i, array_size);

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


void Max_Heapify(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;
  }
}