Введение в сортировку кучи в Java

Heapsort в Java - это метод сортировки, основанный на сравнении, в котором используется структура данных Binary Heap. Эта сортировка почти такая же, как и для сортировки выбора, где будет выбран самый большой элемент, который будет помещен в конец, и процесс будет повторен для всех элементов. Чтобы понять сортировку кучи, давайте посмотрим, что такое двоичная сортировка кучи в Java.

  • Древовидная структура данных.
  • Полное бинарное дерево.
  • Может иметь до двух детей.
  • Значение в корневом узле может быть больше (Max Heap) или меньше (Min Heap)

Как работает сортировка кучи в Java?

Прежде чем перейти к алгоритму, давайте посмотрим, что такое Heapify.

Heapify

После создания кучи с входными данными свойство кучи может не выполняться. Чтобы добиться этого, функция под названием heapify будет использоваться для настройки узлов кучи. Если мы хотим создать максимальную кучу, текущий элемент будет сравниваться с его дочерними элементами, и если значение дочерних элементов больше текущего элемента, будет произведена замена с самым большим элементом в левом или правом дочернем элементе. Точно так же, если нужно создать min-heap, замена будет сделана с наименьшим элементом в левом или правом дочернем элементе. Например, ниже приведен наш входной массив,

Мы можем рассматривать это как дерево вместо массива. Первый элемент будет корневым, второй будет левым дочерним элементом root, третий элемент будет правым корневым и так далее.

Чтобы преобразовать кучу в дерево, пройдите по дереву снизу вверх. Поскольку у конечных узлов нет дочерних элементов, давайте посмотрим на следующий уровень. то есть 5 и 7.

Мы можем начать с 5, как это слева. Здесь у 5 есть два потомка: 9 и 4, где 9 больше, чем родительский узел 5. Чтобы сделать родителей больше, мы поменяем местами 5 и 9. После обмена дерево будет таким, как показано ниже.

Давайте перейдем к следующему элементу 7, где 8 и 2 - дочерние элементы. Аналогично элементам 9 и 4, 7 и 8 поменяются местами, как показано в дереве ниже.

Наконец, у 3 есть двое детей - 9 и 8, где 9 больше среди детей и корня. Таким образом, обмен 3 и 9 будет сделан, чтобы сделать корень больше. Повторяйте процесс, пока не сформируется правильная куча, как показано ниже.

Алгоритм сортировки кучи в порядке возрастания

  1. Создать Max Heap с входными данными
  2. Заменить последний элемент на самый большой элемент в куче
  3. Heapify Tree
  4. Повторите процесс, пока массив не будет отсортирован

Алгоритм сортировки кучи по убыванию

  1. Создать Min Heap с входными данными
  2. Заменить последний элемент наименьшим элементом в куче
  3. Heapify Tree
  4. Повторите процесс, пока массив не будет отсортирован

Теперь попробуем отсортировать полученную выше кучу в порядке возрастания, используя данный алгоритм. Сначала удалите самый большой элемент. т.е. корень и заменить его на последний элемент.

Теперь сложите сформированное дерево и вставьте удаленный элемент в последний массив, как показано ниже.

Снова удалите корневой элемент, замените его последним элементом и сложите его.

Вставьте удаленный элемент в свободное место. Теперь вы можете видеть, что конец массива сортируется.

Теперь удалите элемент 7 и замените его на 2.

Кучи дерева, как показано ниже.

Повторяйте процесс, пока массив не будет отсортирован. Извлечение элемента 5.

Куча дерева.

Извлечение элемента 4.

Снова ворох.

Наконец, отсортированный массив будет сформирован.

Примеры реализации сортировки кучи в Java

Теперь давайте посмотрим на исходный код сортировки кучи на Java

//Java program to sort the elements using Heap sort
import java.util.Arrays;
public class HeapSort (
public void sort(int array()) (
int size = array.length; //Assigning the length of array in a variable
// Create heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(array, size, i);
//Find the maximum element and replace it with the last element in the array
for (int i=size-1; i>=0; i--) (
int x = array(0);//largest element(It is available in the root)
array(0) = array(i);
array(i) = x;
// Recursively call heapify until a heap is formed
heapify(array, i, 0);
)
)
// Heapify function
void heapify(int array(), int SizeofHeap, int i) (
int largestelement = i; // Set largest element as root
int leftChild = 2*i + 1; // index of left child = 2*i + 1
int rightChild = 2*i + 2; //index of right child = 2*i + 2
// left child is greater than root
if (leftChild array(largestelement))
largestelement = leftChild ;
//right child is greater than largest
if (rightChild array(largestelement))
largestelement = rightChild ;
// If largestelement is not root
if (largestelement != i) (
int temp = array(i);
array(i) = array(largestelement);
array(largestelement) = temp;
// Recursive call to heapify the sub-tree
heapify(array, SizeofHeap, largestelement);
)
)
public static void main(String args()) (
int array() = (3, 5, 7, 9, 4, 8, 2);
System. out .println("Input array is: " + Arrays. toString (array));
HeapSort obj = new HeapSort();
obj.sort(array);
System. out .println("Sorted array is : " + Arrays. toString (array));
)
)

Выход

Вывод

Сортировка кучи - это метод сортировки, который зависит от структуры двоичных данных кучи. Это почти похоже на сортировку выбора и не использует отдельные массивы для сортировки и кучи.

Рекомендуемая статья

Это было руководство по сортировке кучи на Java. Здесь мы обсуждаем рабочий алгоритм сортировки по возрастанию и убыванию и примеры с примером кода. Вы также можете просмотреть наши другие предлагаемые статьи, чтобы узнать больше -

  1. Математические функции JavaScript
  2. Макет в Java
  3. Компиляторы Java
  4. Руководство по сортировке слиянием в Java
  5. Руководство по сортировке кучи в C
  6. Примеры сортировки кучи в C ++

Категория:

Разработка программного обеспечения