Увод у хеап сортирање на Јави

Хеапсорт у Јави је техника поређења заснована на поређењу, где се користи структура података Бинари Хеап. Ово сортирање је готово исто као у селекцијској врсти где ће бити изабран највећи елемент и постављен на крају, а поступак ће се поновити за све елементе. Да бисмо разумели сорту хеап-а, да видимо шта је Бинарни скуп хеап-а у Јави

  • Структура података заснована на дрвету.
  • Комплетно бинарно дрво.
  • Може имати до двоје деце.
  • Вриједност у коријенском чвору може бити већа (Мак Хеап) или Мања (Мин Хеап)

Како Хеап Сорт дјелује на Јави?

Пре него што пређемо на алгоритам, да видимо шта је Хеапифи.

Хеапифи

Након што се створи гомила са улазним подацима, својство гомиле можда неће бити задовољено. Да би се постигла, функција која се зове хеапифи користиће се за подешавање чворова у хрпи. Ако желимо да створимо мак хеап, тренутни елемент ће се упоређивати са његовом децом и ако је вредност деце већа од тренутног елемента, замена ће се обавити са највећим елементом у левом или десном детету. Слично томе, ако је потребно створити мин-хеап, замена ће се обавити са најмањим елементом код детета лево или десно. На пример, Следеће је наш улазни низ,

Ово можемо сматрати стаблом уместо низа. Први елемент ће бити корен, други ће бити лево дете корена, трећи ће бити дете дете корена и тако даље.

Да бисте преобразили гомилу у дрво, пређите дрво у правцу одоздо према горе. Пошто чворови листова немају децу, погледајмо на следећи ниво. тј. је 5 и 7.

Можемо почети у 5 као што је то са леве стране. Овде 5 има двоје деце: 9 и 4, где је 9 веће од родитељског чвора 5. Да бисмо повећали родитеље, заменит ћемо 5 и 9. Након замене, дрво ће бити као што је приказано у наставку.

Идемо на следећи елемент 7 где су 8 и 2 деца. Слично елементима 9 и 4, 7 и 8 ће бити замењени као у доњем стаблу.

Коначно, 3 има двоје деце - 9 и 8 где је 9 веће међу децом и коренима. Дакле, замена 3 и 9 ће се обавити како би се корен повећао. Понављајте поступак док се не формира валидна хрпа као што је приказано у наставку.

Алгоритам за хрпу Сортирај узлазним редоследом

  1. Креирајте Мак Хеап са улазним подацима
  2. Замените последњи елемент са највећим елементом у хрпи
  3. Угаси дрво
  4. Понављајте поступак док се низ не сортира

Алгоритам за хрпу Поредај по силазном редоследу

  1. Креирајте Мин Хеап са улазним подацима
  2. Замените последњи елемент најмањим елементом у хрпи
  3. Угаси дрво
  4. Понављајте поступак док се низ не сортира

Сада покушајмо да сортирамо горе добијену Хеап у узлазном редоследу користећи задани алгоритам. Прво уклоните највећи елемент. тј. роот и замените га последњим елементом.

Сада упишите формирано стабло и уметните уклоњени елемент у последњи низ као што је приказано у наставку

Опет уклоните коријенски елемент, замијените га посљедњим елементом и умотајте га.

Уметните уклоњени елемент у слободно место. Сада можете видети да је крај матрице сређен.

Уклоните елемент 7 и замените га са 2.

Игрејте дрво, као што је приказано испод.

Понављајте поступак док се низ не сортира. Уклањање елемента 5.

Огревање дрвета.

Уклањање елемента 4.

Опет грејан.

Напокон ће се формирати овако сортирани низ.

Примери за имплементацију сортирања хеап у Јава

Сада, да видимо изворни код сортирања хеап-а на Јави

//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));
)
)

Излаз

Закључак

Хеап Сорт је техника сортирања која зависи од структуре Бинарних хеап података. Скоро је слична селекцији и не користи одвојене низове за разврставање и скупљање.

Препоручени чланак

Ово је водич за сортирање хеап-а на Јави. Овде смо расправљали о раду, сортирању алгоритма узлазним и силазним редоследом и примерима са узорком кода. Можете и да прођете кроз друге наше предложене чланке да бисте сазнали више -

  1. ЈаваСцрипт математичке функције
  2. Изглед у Јави
  3. Јава компајлери
  4. Водич за спајање сортирања у Јави
  5. Водич за сортирање хеап у Ц
  6. Примери сортирања хеап у Ц ++

Категорија:

Развој софтвера