Въведение в сортирането в купа на Java

Heapsort в Java е метод за сортиране, базиран на сравнение, където се използва структура на данни Binary Heap. Това сортиране е почти същото като сортирането на селекция, при което ще бъде избран най-големият елемент и поставен в края и процесът ще бъде повторен за всички елементи. За да разберем сортирането на Heap, нека да видим какво бинарно сортиране в Java.

  • Структура на данни на базата на дърво.
  • Пълно бинарно дърво.
  • Може да има до две деца.
  • Стойността в коренния възел може да бъде по-голяма (Max Heap) или по-малка (Min Heap)

Как работи сортирането Heap в Java?

Преди да преминем към алгоритъма, нека да видим какво е Heapify.

Heapify

След като се създаде купчина с входните данни, свойството heap може да не бъде удовлетворено. За да се постигне това, функция, наречена heapify, ще се използва за регулиране на възлите на грамадата. Ако искаме да създадем max heap, текущият елемент ще бъде сравнен с неговите деца и ако стойността на децата е по-голяма от текущия елемент, смяната ще се извърши с най-големия елемент в ляво или дясно дете. По подобен начин, ако е необходимо да се създаде min-heap, подмяната ще се извърши с най-малкия елемент в лявото или дясното дете. Например, по-долу е нашият входен масив,

Можем да разгледаме това като дърво вместо масив. Първият елемент ще бъде root, вторият ще бъде лявото дете на root, третият елемент ще бъде дясното дете на root и така нататък.

За да трансформирате купчина в дърво, пресечете дървото в посока отдолу нагоре. Тъй като листните възли нямат деца, нека разгледаме следващото ниво. т.е. е 5 и 7.

Можем да започнем в 5, както е отляво. Тук 5 има две деца: 9 и 4, където 9 е по-голямо от родителския възел 5. За да увеличим родителите, ще разменим 5 и 9. След размяна, дървото ще бъде както е показано по-долу.

Нека преминем към следващия елемент 7, където 8 и 2 са децата. Подобно на елементите 9 и 4, 7 и 8 ще бъдат разменени, както в долното дърво.

И накрая, 3 имат две деца - 9 и 8, където 9 е по-голямо сред децата и корена. Така че ще се извърши размяна на 3 и 9, за да се увеличи коренът. Повторете процеса, докато не се формира валидна купчина, както е показано по-долу.

Алгоритъм за Heap Сортиране във възходящ ред

  1. Създайте Max Heap с входните данни
  2. Заменете последния елемент с най-големия елемент в грамадата
  3. Надуйте дървото
  4. Повторете процеса, докато масивът не се сортира

Алгоритъм за Heap Сортиране в низходящ ред

  1. Създайте Min Heap с входните данни
  2. Заменете последния елемент с най-малкия елемент в грамадата
  3. Надуйте дървото
  4. Повторете процеса, докато масивът не се сортира

Сега, нека се опитаме да сортираме получената по-горе Heap във възходящ ред, като използваме дадения алгоритъм. Първо, премахнете най-големия елемент. т.е. корен и го заменете с последния елемент.

Сега, натрупайте образуваното дърво и поставете отстранения елемент в последния от масива, както е показано по-долу

Отново премахнете кореновия елемент, заменете го с последния елемент и го надушете.

Поставете отстранения елемент в свободното положение. Сега можете да видите, че краят на масива се сортира.

Сега премахнете елемент 7 и го заменете с 2.

Нагрейте дървото, както е показано по-долу.

Повторете процеса, докато масивът не се сортира. Премахване на елемент 5.

Нагряване на дървото.

Премахване на елемент 4.

Отново загърбва.

Най-сетне ще се формира сортиран масив като този.

Примери за прилагане на сортиране на Heap в Java

Сега, нека да видим изходния код на сортирането Heap в 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));
)
)

продукция

заключение

Heap Sort е техника за сортиране, която зависи от структурата на данните на Binary Heap Data. Той е почти подобен на сортирането на селекцията и не използва отделни масиви за сортиране и натрупване.

Препоръчителен член

Това е ръководство за сортиране на Heap в Java. Тук обсъждаме работещия, сортиране на алгоритъм с възходящ и низходящ ред и примери с примерен код. Можете да разгледате и другите ни предложени статии, за да научите повече -

  1. JavaScript математически функции
  2. Оформление в Java
  3. Java компилатори
  4. Ръководство за сливане Сортиране в Java
  5. Пътеводител за сортирането на купчината в С
  6. Примери за сортиране на купчина в C ++

Категория:

Разработване на софтуер