Java의 힙 정렬

Java의 Heapsort는 데이터 구조 Binary Heap을 사용하는 비교 기반 정렬 기술입니다. 이 정렬은 선택 정렬과 거의 동일합니다. 즉, 가장 큰 요소를 선택하여 마지막에 배치하고 모든 요소에 대해 프로세스를 반복합니다. 힙 정렬(Heap Sort)을 이해하기 위해 자바에서 바이너리 힙 정렬(Binary Heap Sort)이 무엇인지 살펴보겠습니다.

• 트리 기반 데이터 구조.
• 완전한 이진 트리.
• 최대 2명의 자녀를 가질 수 있습니다.
• 루트 노드의 값은 더 크거나(최대 힙) 더 작을 수 있습니다(최소 힙)

Java에서 힙 정렬은 어떻게 작동하나요?

알고리즘으로 넘어가기 전에 Heapify가 무엇인지 알아보겠습니다.

광고 이 카테고리에서 인기 있는 강좌 JAVA MASTERY - 전문 분야 | 78 코스 시리즈 | 15가지 모의고사

힙파이

입력 데이터로 힙이 생성된 후 힙 속성이 충족되지 않을 수 있습니다. 이를 달성하기 위해 heapify라는 함수를 사용하여 힙 노드를 조정합니다. 최대 힙을 생성하려면 현재 요소를 해당 하위 요소와 비교하고, 하위 요소의 값이 현재 요소보다 크면 왼쪽 또는 오른쪽 하위 요소 중 가장 큰 요소로 교체가 수행됩니다. 마찬가지로 최소 힙을 생성해야 하는 경우 왼쪽 또는 오른쪽 자식의 가장 작은 요소로 교체가 수행됩니다. 예를 들어, 다음은 입력 배열입니다.

이를 배열 대신 트리로 간주할 수 있습니다. 첫 번째 요소는 루트가 됩니다. 두 번째는 루트의 왼쪽 자식이 됩니다. 세 번째 요소는 루트의 오른쪽 자식이 됩니다.

힙을 트리로 변환하려면 트리를 상향식 방향으로 순회하세요. 리프 노드에는 자식이 없으므로 다음 레벨을 살펴보겠습니다. 즉, 5와 7입니다.

왼쪽에 있으니 5시부터 시작하시면 됩니다. 여기서 5에는 9와 4라는 두 개의 자식이 있습니다. 여기서 9는 상위 노드 5보다 큽니다. 상위 노드를 더 크게 만들기 위해 5와 9를 교환합니다. 교환 후 트리는 아래와 같습니다.

8과 2가 자식 요소인 다음 요소인 7로 이동하겠습니다. 요소 9와 4와 유사하게, 아래 트리와 같이 요소 7과 8이 교체됩니다.

마지막으로 3에는 9와 8이라는 두 명의 자녀가 있습니다. 여기서 9는 자녀와 루트 중에서 더 큽니다. 따라서 3과 9를 교환하여 루트를 더 크게 만듭니다. 아래와 같이 유효한 힙이 형성될 때까지 이 과정을 반복합니다.

오름차순 힙 정렬 알고리즘

1. 입력 데이터로 최대 힙 생성
2. 마지막 요소를 힙에서 가장 큰 요소로 교체
3. 나무를 히피파이
4. 배열이 정렬될 때까지 이 과정을 반복하세요

내림차순 힙 정렬 알고리즘

1. 입력 데이터로 최소 힙 생성
2. 마지막 요소를 힙에서 가장 작은 요소로 교체
3. 나무를 히피파이
4. 배열이 정렬될 때까지 이 과정을 반복하세요

이제 주어진 알고리즘을 사용하여 위에서 얻은 힙을 오름차순으로 정렬해 보겠습니다. 먼저 가장 큰 요소를 제거합니다. 즉, 루트를 만들고 마지막 요소로 바꿉니다.

이제 아래와 같이 형성된 트리를 힙화하고 제거된 요소를 배열의 마지막에 삽입합니다.

다시 루트 요소를 제거하고 마지막 요소로 교체한 후 힙화합니다.

제거된 요소를 빈 위치에 삽입합니다. 이제 배열의 끝부분이 정렬되는 것을 볼 수 있습니다.

이제 요소 7을 제거하고 요소 2로 바꿉니다.

아래 그림과 같이 트리를 히피화하세요.

배열이 정렬될 때까지 이 과정을 반복합니다. 요소 5를 제거합니다.

나무를 쌓습니다.

요소 4를 제거합니다.

또 힙업 중. 

드디어 이렇게 정렬된 배열이 만들어지게 됩니다.

예

이제 Java의 Heap Sort 소스코드를 살펴보겠습니다

//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 <u>heapify</u> until a heap is formed
heapify(array, i, 0);
}
}
// <u>Heapify</u> 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  < SizeofHeap && array[leftChild ] > array[largestelement])
largestelement = leftChild ;
//right child is greater than largest
if (rightChild  < SizeofHeap && array[rightChild ] > array[largestelement])
largestelement = rightChild ;
// If <u>largestelement</u> 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.<em>out</em>.println("Input array is: " + Arrays.<em>toString</em>(array));
HeapSort obj = new HeapSort();
obj.sort(array);
System.<em>out</em>.println("Sorted array is : " + Arrays.<em>toString</em>(array));
}
}

출력

결론

힙 정렬은 바이너리 힙 데이터 구조에 따른 정렬 기술입니다. 선택 정렬과 거의 유사하며 정렬과 힙에 별도의 배열을 사용하지 않습니다.

 추천 기사

Java의 힙 정렬에 대한 안내였습니다. 여기에서는 오름차순 및 내림차순을 사용한 정렬 알고리즘과 샘플 코드가 포함된 예제에 대해 설명합니다. 또한 다른 추천 도움말을 통해 자세히 알아볼 수도 있습니다.

1. Java의 병합 정렬
2. C의 힙 정렬
3. C++의 힙 정렬
4. 데이터 구조의 선택 정렬

위 내용은 Java의 힙 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!