Wprowadzenie do Heap Sort In Java

Heapsort w Javie jest techniką sortowania opartą na porównaniu, w której stosuje się strukturę danych Binary Heap. To sortowanie jest prawie takie samo jak sortowanie selekcji, w którym zostanie wybrany największy element i zostanie umieszczony na końcu, a proces zostanie powtórzony dla wszystkich elementów. Aby zrozumieć Sortowanie sterty, zobaczmy, co to jest Binary Heap Sort w Javie.

  • Drzewna struktura danych.
  • Kompletne drzewo binarne.
  • Może mieć maksymalnie dwoje dzieci.
  • Wartość w węźle głównym może być większa (Max Heap) lub mniejsza (Min Heap)

Jak działa Heap Sort w Javie?

Zanim przejdziemy do algorytmu, zobaczmy, co to jest Heapify.

Heapify

Po utworzeniu sterty z danymi wejściowymi właściwość sterty może nie być spełniona. Aby to osiągnąć, zostanie użyta funkcja o nazwie heapify do dostosowania węzłów stosu. Jeśli chcemy utworzyć maksymalną stertę, bieżący element zostanie porównany z jego elementami potomnymi, a jeśli wartość elementów potomnych będzie większa niż element bieżący, zamiana zostanie wykonana z największym elementem w lewym lub prawym elemencie potomnym. Podobnie, jeśli konieczne jest utworzenie min-sterty, zamiana zostanie wykonana z najmniejszym elementem w lewym lub prawym podrzędnym. Na przykład, oto nasza tablica wejściowa,

Możemy uznać to za drzewo zamiast tablicy. Pierwszy element będzie rootem, drugi będzie lewym dzieckiem root, trzeci element będzie prawym dzieckiem root i tak dalej.

Aby przekształcić stertę w drzewo, przejdź przez drzewo od dołu do góry. Ponieważ węzły liści nie mają dzieci, przejdźmy do następnego poziomu. to jest 5 i 7.

Możemy zacząć od 5, tak jak jest po lewej stronie. Tutaj 5 ma dwoje dzieci: 9 i 4, gdzie 9 jest większe niż węzeł nadrzędny 5. Aby powiększyć rodziców, zamienimy 5 i 9. Po zamianie drzewo będzie wyglądało jak pokazano poniżej.

Przejdźmy do następnego elementu 7, w którym 8 i 2 to dzieci. Podobnie jak elementy 9 i 4, 7 i 8 zostaną zamienione jak w poniższym drzewie.

Wreszcie, 3 ma dwoje dzieci - 9 i 8, gdzie 9 jest większe wśród dzieci i korzeni. Tak więc zamiana 3 i 9 zostanie wykonana, aby root był większy. Powtarzaj proces do momentu utworzenia prawidłowej sterty, jak pokazano poniżej.

Algorytm sortowania sterty w porządku rosnącym

  1. Utwórz Max Heap z danymi wejściowymi
  2. Zastąp ostatni element największym elementem w stercie
  3. Heapify the Tree
  4. Powtarzaj proces, aż tablica zostanie posortowana

Algorytm sortowania sterty w porządku malejącym

  1. Utwórz minimalny stos z danymi wejściowymi
  2. Zastąp ostatni element najmniejszym elementem w stercie
  3. Heapify the Tree
  4. Powtarzaj proces, aż tablica zostanie posortowana

Teraz spróbujmy posortować otrzymaną powyżej Stertę w porządku rosnącym, używając podanego algorytmu. Najpierw usuń największy element. tzn. zrootować i zastąpić go ostatnim elementem.

Teraz ułóż utworzone drzewo w stos i wstaw usunięty element do ostatniego elementu tablicy, jak pokazano poniżej

Ponownie usuń element główny, zastąp go ostatnim elementem i Heapify.

Włóż usunięty element do pustej pozycji. Teraz możesz zobaczyć, że koniec tablicy jest sortowany.

Teraz usuń element 7 i zastąp go 2.

Heapify drzewa, jak pokazano poniżej.

Powtarzaj proces, aż tablica zostanie posortowana. Usuwanie elementu 5.

Heapifying the tree.

Usuwanie elementu 4.

Znowu się kłania.

W końcu powstanie taka posortowana tablica.

Przykłady implementacji sortowania sterty w Javie

Zobaczmy teraz kod źródłowy Heap Sort w Javie

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

Wynik

Wniosek

Sortowanie sterty to technika sortowania, która zależy od struktury danych binarnych sterty. Jest prawie podobny do sortowania selekcyjnego i nie używa osobnych tablic do sortowania i sterty.

Polecany artykuł

To był przewodnik po Heap Sort w Javie. Tutaj omawiamy działający, sortujący algorytm z rosnącą i malejącą kolejnością oraz przykłady z przykładowym kodem. Możesz także przejrzeć nasze inne sugerowane artykuły, aby dowiedzieć się więcej -

  1. Funkcje matematyczne JavaScript
  2. Układ w Javie
  3. Kompilatory Java
  4. Przewodnik po scalaniu Sortuj w Javie
  5. Przewodnik po sortowaniu stosów w C
  6. Przykłady sortowania sterty w C ++

Kategoria:

Rozwój oprogramowania