CIYAWASAY

《Heap Sort》

return └i/2┘

return 2i

return 2i+1

l←Left(i)
r←Right(i)

if l≦heap-size[A] and A[l]>A[i]
   then largest←l

   else largest←i
if r≦heap-size[A] and A[r]>A[largest]
   then largest←r

if largest≠i
   then exchange A[i]←→A[largest]
      Max-Heapify(A,largest)

heap-size[A]←length[A]
for i←└length[A]/2┘ downto 1
   do Max-Heapify(A,i)

Build-Max-Heap(A)
for i ←length[A] downto 2
   do exchange A[1]←→A[i]
      heap-size[A]←heap-size[A]-1
   Max-Heapify(A,1)

int parent(int i){
   return (i - 1)/2;
}

int left(int i){
   return 2 * i + 1;
}

int right(int i){
   return 2 * i + 2;
}

void heapSort(int[] Array){
   buildMaxHeap( Array );
   for(int i = Array.length - 1; i >= 1; i--){
      int temp = Array[0]; Array[0] = Array[i]; Array[i] = temp;
      heapSize--;
      maxHeapify(Array, 0);
   }
}

void buildMaxHeap(int[] Array){
   heapSize = Array.length;
   for(int i = (int)( (Array.length/2) - 1 ); i >= 0; i--){
      maxHeapify(Array, i);
   }
}

void maxHeapify(int[] Array, int i){
   int L = left(i);
   int R = right(i);
   int largest;
   if( (L < heapSize) && (Array[L] > Array[i]) )
      largest = L;
   else
      largest = i;
   if( (R < heapSize) && (Array[R] > Array[largest]) )
      largest = R;
   if(largest != i){
      int temp = Array[i]; Array[i] = Array[largest];
      Array[largest] = temp;
      maxHeapify(Array, largest);
   }
}

int parent(int i){
   return (i - 1)/2;
}

int left(int i){
   return 2 * i + 1;
}

int right(int i){
   return 2 * i + 2;
}

void buildMaxHeap(String[] Array) {
   heapSize = Array.length;

   for (int i = (int) ((Array.length / 2) - 1); i >= 0; i--) {
      maxHeapify(Array, i);
   }
}

void maxHeapify(String[] Array, int i) {
   int L = left(i);
   int R = right(i);
   int largest;

   if ((L < heapSize) && (Array[L].name.compareTo(Array[i].name) > 0)) {
      largest = L;
   } else {
      largest = i;
   }

   if ((R < heapSize) && (Array[R].name.compareTo(Array[largest].name) > 0)) {
      largest = R;
   }

   if (largest != i) {
      String temp = Array[i].name;
      Array[i].name = Array[largest].name;
      Array[largest].name = temp;
      maxHeapify(Array, largest);
   }
}


void heapSort(String[] Array) {
   buildMaxHeap(Array);

   for (int i = Array.length - 1; i >= 1; i--) {
      String temp = Array[0].name;
      Array[0].name = Array[i].name;
      Array[i].name = temp;
      heapSize--;
      maxHeapify(Array, 0);
   }
}

# posted by SwanBear @ 00:23