ヒープソートを使用してJavaでソートする

Question

import java.util.Arrays; 

public class Test{ 

//main method 
public static void main(String... args){ 
    int[] a = new int[]{16,14,10,8,7,9,3,2,4,1}; 

    System.out.println("unsorted array " + Arrays.toString(a)); 

    heap_sort(a); 

    System.out.println("Sorted array " + Arrays.toString(a)); 
} 

//returns left child index of given index 
private static int left_child(int i){ 
return (i * 2 + 1); 
} 

//returns right child index of the given index 
private static int right_child(int i){ 
    return (i * 2 + 2); 
} 


public static void max_heapify(int[] array , int index , int heap_size){ 
    int largest = index; 
    int left = left_child(index); 
    int right = right_child(index); 

    if(left < heap_size && array[left] > array[index]){ 
     largest = left; 
    } 
    else largest = index; 

    if (right < heap_size && array[right] > array[largest]){ 
     largest = right; 
    } 

    if(largest != index){ 
     //exchange array[index] with array[largest] 
     int a = array[index]; 
     array[index] = array[largest]; 
     array[largest] = a; 

     max_heapify(array,largest,heap_size); 
    } 
} 

public static void build_max_heap(int[] array){ 
    int heap_size = array.length - 1; 


    for (int i = ((array.length - 1)/2) ; i >= 0 ; i--){ 
     max_heapify(array, i, heap_size); 
    } 
} 

//main heap sort function 
public static void heap_sort(int[] array){ 

    int heap_size = array.length - 1; 


    build_max_heap(array); 

    for(int i = (array.length - 1) ; i > 0 ; i--){ 
     //exchange array[0] with array[i] 
     int a = array[0]; 
     array[0] = array[i]; 
     array[i] = a; 

     heap_size = heap_size - 1; 
     max_heapify(array , 1 , heap_size); 
    } 
} 


} 

ほとんどすべての可能性を試しましたが、うまく動作しません。私はどこが間違っているかを知ることができますか？ 私のコードの出力は 未整列配列[16,14,10,8,7,9,3,2,4,1] ソート配列[14,10,8,7,9,3,2,4 、1、16]

Answer 1

左と右の子でなければなりませんので、問題が緩んでアイテムということである。

//returns left child index of given index 
private static int left_child(int i){ 
return (i * 2); 
} 

//returns right child index of the given index 
private static int right_child(int i){ 
    return (i * 2 + 1); 
} 

Answer 2

いくつかの問題があります。 - あなたが最初の緩いので、左と右の子が変更されています配列内の要素です。 - max_heapify関数では、ループは< = です。 - heap_sort関数では、max_heapify関数に1の代わりに0を渡す必要があります。

//returns left child index of given index 
    private static int left_child(int i) 
    { 
     return (i * 2); 
    } 

    //returns right child index of the given index 
    private static int right_child(int i) 
    { 
     return (i * 2 + 1); 
    } 

    public static void max_heapify(int[] array, int index, int heap_size) 
    { 
     int largest = index; 
     int left = left_child(index); 
     int right = right_child(index); 

     if (left <= heap_size && array[left] > array[index]) 
     { 
      largest = left; 
     } 

     if (right <= heap_size && array[right] > array[largest]) 
     { 
      largest = right; 
     } 

     if (largest != index) 
     { 
      //exchange array[index] with array[largest] 
      int a = array[index]; 
      array[index] = array[largest]; 
      array[largest] = a; 

      max_heapify(array, largest, heap_size); 
     } 
    } 

    public static void build_max_heap(int[] array) 
    { 
     int heap_size = array.length - 1; 


     for (int i = ((array.length - 1)/2); i >= 0; i--) 
     { 
      max_heapify(array, i, heap_size); 
     } 
    } 

    //main heap sort function 
    public static void heap_sort(int[] array) 
    { 

     int heap_size = array.Length - 1; 


     build_max_heap(array); 

     for (int i = (array.Length - 1); i > 0; i--) 
     { 
      //exchange array[0] with array[i] 
      int a = array[0]; 
      array[0] = array[i]; 
      array[i] = a; 

      heap_size = heap_size - 1; 
      max_heapify(array, 0, heap_size); 
     } 
    }