Перейти к контенту

Пирамидальная сортировка массива в Java

Ниже приведен алгоритм пирамидальной сортировки (maxheap) на массиве в Java.

  1. Создание нового узла в конце кучи.
  2. Присвоить новое значение узла.
  3. Сравните значение этого дочернего узла с его родителем.
  4.  Если значение родителя меньше, чем у ребенка, а затем поменять их местами.
  5. Повторите шаг 3 до 4 кучного свойство не выполняется.

Пример

import java.util.Arrays;
import java.util.Scanner;

public class Heapsort {
   public static void heapSort(int[] myArray, int length) {
      int temp;
      int size = length-1;
      for (int i = (length / 2); i >= 0; i--) {
         heapify(myArray, i, size);
      };
      for(int i= size; i>=0; i--) {
         temp = myArray[0];
         myArray[0] = myArray[size];
         myArray[size] = temp;
         size--;
         heapify(myArray, 0, size);
      }
      System.out.println(Arrays.toString(myArray));
   }
   public static void heapify (int [] myArray, int i, int heapSize) {
      int a = 2*i;
      int b = 2*i+1;
      int largestElement;
      if (a<= heapSize  myArray[a] > myArray[i]) {
         largestElement = a;
      } else {
         largestElement = i;
      }
      if (b <= heapSize  myArray[b] > myArray[largestElement]) {
         largestElement = b;
      }
      if (largestElement != i) {
         int temp = myArray[i];
         myArray[i] = myArray[largestElement];
         myArray[largestElement] = temp;
         heapify(myArray, largestElement, heapSize);
     }
   }
   public static void main(String args[]) {
      Scanner scanner = new Scanner(System.in);
      System.out.println("Enter the size of the array :: ");
      int size = scanner.nextInt();
      System.out.println("Enter the elements of the array :: ");
      int[] myArray = new int[size];
      for(int i=0; i<size; i++) {
         myArray[i] = scanner.nextInt();
      }
      heapSort(myArray, size);
   }
}

Итог

Enter the size of the array ::
5
Enter the elements of the array ::
45
125
44
78
1
[1, 44, 45, 78, 125]

Оцени статью

 

Средняя оценка / 5. Количество голосов:

Спасибо, помогите другим - напишите комментарий, добавьте информации к статье.

Или поделись статьей

Видим, что вы не нашли ответ на свой вопрос.

Помогите улучшить статью.

 

Пока нет комментариев.

Добавить комментарий

Ваш e-mail не будет опубликован.

СайдбарКомментарии (0)