Как создать метод minHeapify, который принимает массив и выполняет ли все действия minHeapify в одном методе? - PullRequest
Новая
       23

Как создать метод minHeapify, который принимает массив и выполняет ли все действия minHeapify в одном методе?

0 голосов
/ 01 апреля 2020

Мне дали приведенный ниже код для начала, когда я мог редактировать только в методе minHeapify (), так как это разрешено нашим учителем: 

        class Main {
      /**
       * main will test if minHeapify properly outputs the array representation of a heap
       * made from the elements of array unsorted
       */
      public static void main(String[] args)
      {
        int[] unsorted = new int[]{93,25,67,6,12,78,59};
        int[] heaped = minHeapify(unsorted);

        for(int i = 0; i < unsorted.length; i++)
        {
          System.out.print(unsorted[i] + " ");
        }

        System.out.println();

        for(int i = 0; i < heaped.length; i++)
        {
          System.out.print(heaped[i] + " ");
        }
      }

      /**
       * Takes in an unsorted array of integers and outputs the array representation of a
       * min heap made with with those elements.
       * 
       * minHeapify will take the elements from the unsorted array starting from index 0.
       * 
       * @parameter arr the array of unsorted ints
       * @return heapArr the array representaion of a heap made from the elements of arr
       */
      public static int[] minHeapify(int[] arr)
      {
        int[] heapArr = new int[arr.length];

        return heapArr;
      }
    }

Я пытался сделать то, что ниже поскольку я не уверен, какой подход использовать, кроме как с циклами for () и попыткой найти значения "parent" и "children". Наш учитель дает нам мало информации о том, что делать, поэтому я подумал, что циклически проверять наличие родителей и левых / правых детей и сравнивать их было бы способом go: 

    public static int[] minHeapify(int[] arr)
  {
    int[] heapArr = new int[arr.length];
    int maxIndex = heapArr.length-1;

    while(heapArr[maxIndex] != null){
    for(int i = 1; i < heapArr.length; i++){
        int parent = heapArr[(i-1)/2];
        int left = heapArr[(i*2)+1];
        int right = heapArr[(i*2)+2];

        if(parent > left || parent > right)
            if(left < right){
                int tmp = parent;
                parent = left;
                left = tmp;
            }
            else if( right < left){
                int tmp = parent;
                parent = right;
                right = tmp;
            }
            heapArr[i] = parent;
            heapArr[i+1] = left;
            heapArr[i+2] = right;
    }
    }

    return heapArr; }

Я видел несколько способов создания класса для minHeapify с несколькими методами, но ни один из них не использует один метод для выполнения процесса. Пожалуйста, помогите.

...