힙 정렬 비교 기반 정렬 기술은 바이너리 힙 데이터 구조. 이는 다음과 유사합니다. 선택 정렬 여기서 먼저 최소 요소를 찾고 최소 요소를 시작 부분에 배치합니다. 나머지 요소에 대해서도 동일한 과정을 반복합니다.
힙 정렬 알고리즘
문제를 해결하려면 아래 아이디어를 따르십시오.
권장 문제 문제 해결로 넘어가기 전에 먼저 PRACTICE에서 문제를 해결하세요.먼저 heapify를 사용하여 배열을 힙 데이터 구조로 변환한 다음 Max-heap의 루트 노드를 하나씩 삭제하고 이를 힙의 마지막 노드로 바꾼 다음 힙의 루트를 힙화합니다. 힙 크기가 1보다 커질 때까지 이 과정을 반복합니다.
- 주어진 입력 배열에서 힙을 만듭니다.
- 힙에 요소가 하나만 포함될 때까지 다음 단계를 반복합니다.
- 힙의 루트 요소(가장 큰 요소)를 힙의 마지막 요소와 바꿉니다.
- 힙의 마지막 요소(현재 올바른 위치에 있음)를 제거합니다.
- 힙의 나머지 요소를 힙화합니다.
- 정렬된 배열은 입력 배열의 요소 순서를 반대로 하여 얻습니다.
힙 정렬의 세부 작업
힙 정렬을 더 명확하게 이해하기 위해 정렬되지 않은 배열을 힙 정렬을 사용하여 정렬해 보겠습니다.
배열을 생각해 보세요: arr[] = {4, 10, 3, 5, 1}.완전한 이진 트리 구축: 배열에서 완전한 이진 트리를 구축합니다.
힙 정렬 알고리즘 | 완전한 이진 트리 구축
최대 힙으로 변환: 그 후, 작업은 정렬되지 않은 배열에서 트리를 구성하고 이를 다음으로 변환하는 것입니다. 최대 힙.
- 힙을 최대 힙으로 변환하려면 상위 노드가 항상 하위 노드보다 크거나 같아야 합니다.
- 이 예에서는 상위 노드로 4 자식 노드보다 작습니다. 10, 따라서 이를 교환하여 최대 힙을 구축합니다.
- 지금, 4 부모가 자식보다 작기 때문에 5 , 따라서 이 두 가지를 다시 교체하면 결과 힙과 배열은 다음과 같아야 합니다.
힙 정렬 알고리즘 | Max Heapify가 생성한 이진 트리
힙 정렬을 수행합니다. 각 단계에서 최대 요소를 제거(즉, 끝 위치로 이동하여 제거)한 다음 나머지 요소를 고려하여 최대 힙으로 변환합니다.
- 루트 요소 삭제 (10) 최대 힙에서. 이 노드를 삭제하려면 마지막 노드와 교체해 보십시오. (1). 루트 요소를 제거한 후 다시 힙화하여 최대 힙으로 변환합니다.
- 결과 힙과 배열은 다음과 같아야 합니다.
힙 정렬 알고리즘 | 루트 및 최대 힙에서 최대값 제거
- 위 단계를 반복하면 다음과 같은 모습이 됩니다.
힙 정렬 알고리즘 | 루트에서 다음 최대값 제거 nad max heapify
- 이제 루트(예: 3)를 다시 제거하고 heapify를 수행합니다.
힙 정렬 알고리즘 | 이전 단계 반복
- 이제 루트가 다시 제거되면 정렬됩니다. 정렬된 배열은 다음과 같습니다. arr[] = {1, 3, 4, 5, 10} .
힙 정렬 알고리즘 | 최종 정렬된 배열
힙 정렬 구현
C++ // C++ program for implementation of Heap Sort #include using namespace std; // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) { // Initialize largest as root int largest = i; // left = 2*i + 1 int l = 2 * i + 1; // right = 2*i + 2 int r = 2 * i + 2; // If left child is larger than root if (l < N && arr[l]>arr[최대]) 최대 = l; // 오른쪽 자식이 가장 큰 것보다 큰 경우 // 지금까지는 if (r< N && arr[r]>arr[최대]) 최대 = r; // maximum이 루트가 아닌 경우 if (largest != i) { swap(arr[i], arr[largest]); // 영향을 받은 하위 트리를 반복적으로 힙화합니다. // heapify(arr, N, maximum); } } // 힙 정렬을 수행하는 주요 함수 void heapSort(int arr[], int N) { // 힙 구축(배열 재정렬) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // 힙에서 // 요소를 하나씩 추출합니다. for (int i = N - 1; i> 0; i--) { // 현재 루트를 끝으로 이동합니다. swap(arr[0], arr[i]); // 감소된 힙에서 최대 heapify를 호출합니다. heapify(arr, i, 0); } } // n 크기의 배열을 인쇄하는 유틸리티 함수 void printArray(int arr[], int N) { for (int i = 0; i< N; ++i) cout << arr[i] << ' '; cout << '
'; } // Driver's code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call heapSort(arr, N); cout << 'Sorted array is
'; printArray(arr, N); }> 씨 // Heap Sort in C #include // Function to swap the position of two elements void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) { // Find largest among root, // left child and right child // Initialize largest as root int largest = i; // left = 2*i + 1 int left = 2 * i + 1; // right = 2*i + 2 int right = 2 * i + 2; // If left child is larger than root if (left < N && arr[left]>arr[가장 큰]) 가장 큰 = 왼쪽; // 오른쪽 자식이 가장 큰 것보다 큰 경우 // 지금까지 if (오른쪽< N && arr[right]>arr[가장 큰]) 가장 큰 = 오른쪽; // 교체하고 계속 힙화함 // 루트가 가장 크지 않은 경우 // 최대값이 루트가 아닌 경우 if (largest != i) { swap(&arr[i], &arr[largest]); // 영향을 받은 하위 트리를 반복적으로 힙화합니다. // heapify(arr, N, maximum); } } // 힙 정렬을 수행하는 주요 함수 void heapSort(int arr[], int N) { // 최대 힙 구축 for (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i); // 힙 정렬 for (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]); // 루트 요소를 Heapify // 다시 루트에서 가장 높은 요소를 가져오기 위해 // 다시 heapify(arr, i, 0); } } // n 크기의 배열을 인쇄하는 유틸리티 함수 void printArray(int arr[], int N) { for (int i = 0; i< N; i++) printf('%d ', arr[i]); printf('
'); } // Driver's code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call heapSort(arr, N); printf('Sorted array is
'); printArray(arr, N); } // This code is contributed by _i_plus_plus_.> 자바 // Java program for implementation of Heap Sort public class HeapSort { public void sort(int arr[]) { int N = arr.length; // Build heap (rearrange array) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // 힙에서 요소를 하나씩 추출합니다. for (int i = N - 1; i> 0; i--) { // 현재 루트를 끝으로 이동 int temp = arr[0]; arr[0] = arr[i]; arr[i] = 온도; // 감소된 힙에서 최대 heapify를 호출합니다. heapify(arr, i, 0); } } // arr[]의 인덱스인 // 노드 i를 루트로 하는 하위 트리를 힙화합니다. n은 힙의 크기입니다. void heapify(int arr[], int N, int i) { int maximum = i; // 루트로 가장 큰 값을 초기화합니다. int l = 2 * i + 1; // 왼쪽 = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // 왼쪽 자식이 루트보다 큰 경우 if (l< N && arr[l]>arr[최대]) 최대 = l; // 오른쪽 자식이 지금까지 가장 큰 것보다 큰 경우 if (r< N && arr[r]>arr[최대]) 최대 = r; // maximum이 루트가 아닌 경우 if (largest != i) { int swap = arr[i]; arr[i] = arr[가장 큰]; arr[최대] = 교환; // 영향을 받은 하위 트리를 재귀적으로 힙화합니다. heapify(arr, N, maximum); } } /* n 크기의 배열을 인쇄하는 유틸리티 함수 */ static void printArray(int arr[]) { int N = arr.length; for (int i = 0; i< N; ++i) System.out.print(arr[i] + ' '); System.out.println(); } // Driver's code public static void main(String args[]) { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = arr.length; // Function call HeapSort ob = new HeapSort(); ob.sort(arr); System.out.println('Sorted array is'); printArray(arr); } }> 씨# // C# program for implementation of Heap Sort using System; public class HeapSort { public void sort(int[] arr) { int N = arr.Length; // Build heap (rearrange array) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // 힙에서 요소를 하나씩 추출합니다. for (int i = N - 1; i> 0; i--) { // 현재 루트를 끝으로 이동 int temp = arr[0]; arr[0] = arr[i]; arr[i] = 온도; // 감소된 힙에서 최대 heapify를 호출합니다. heapify(arr, i, 0); } } // arr[]의 인덱스인 // 노드 i를 루트로 하는 하위 트리를 힙화합니다. n은 힙의 크기입니다. void heapify(int[] arr, int N, int i) { int maximum = i; // 루트로 가장 큰 값을 초기화합니다. int l = 2 * i + 1; // 왼쪽 = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // 왼쪽 자식이 루트보다 큰 경우 if (l< N && arr[l]>arr[최대]) 최대 = l; // 오른쪽 자식이 지금까지 가장 큰 것보다 큰 경우 if (r< N && arr[r]>arr[최대]) 최대 = r; // maximum이 루트가 아닌 경우 if (largest != i) { int swap = arr[i]; arr[i] = arr[가장 큰]; arr[최대] = 교환; // 영향을 받은 하위 트리를 재귀적으로 힙화합니다. heapify(arr, N, maximum); } } /* n 크기의 배열을 인쇄하는 유틸리티 함수 */ static void printArray(int[] arr) { int N = arr.Length; for (int i = 0; i< N; ++i) Console.Write(arr[i] + ' '); Console.Read(); } // Driver's code public static void Main() { int[] arr = { 12, 11, 13, 5, 6, 7 }; int N = arr.Length; // Function call HeapSort ob = new HeapSort(); ob.sort(arr); Console.WriteLine('Sorted array is'); printArray(arr); } } // This code is contributed // by Akanksha Rai(Abby_akku)> 자바스크립트 // JavaScript program for implementation // of Heap Sort function sort( arr) { var N = arr.length; // Build heap (rearrange array) for (var i = Math.floor(N / 2) - 1; i>= 0; i--) heapify(arr, N, i); // 힙에서 요소를 하나씩 추출합니다. for (var i = N - 1; i> 0; i--) { // 현재 루트를 끝으로 이동 var temp = arr[0]; arr[0] = arr[i]; arr[i] = 온도; // 감소된 힙에서 최대 heapify를 호출합니다. heapify(arr, i, 0); } } // arr[]의 인덱스인 // 노드 i를 루트로 하는 하위 트리를 힙화합니다. n은 힙의 크기입니다. function heapify(arr, N, i) { var maximum = i; // 루트로 가장 큰 값을 초기화합니다. var l = 2 * i + 1; // 왼쪽 = 2*i + 1 var r = 2 * i + 2; // right = 2*i + 2 // 왼쪽 자식이 루트보다 큰 경우 if (l< N && arr[l]>arr[최대]) 최대 = l; // 오른쪽 자식이 지금까지 가장 큰 것보다 큰 경우 if (r< N && arr[r]>arr[최대]) 최대 = r; // maximum이 루트가 아닌 경우 if (largest != i) { var swap = arr[i]; arr[i] = arr[가장 큰]; arr[최대] = 교환; // 영향을 받은 하위 트리를 재귀적으로 힙화합니다. heapify(arr, N, maximum); } } /* 크기 n의 배열을 인쇄하는 유틸리티 함수 */ function printArray(arr) { var N = arr.length; for (var i = 0; i< N; ++i) document.write(arr[i] + ' '); } var arr = [12, 11, 13, 5, 6, 7]; var N = arr.length; sort(arr); document.write( 'Sorted array is'); printArray(arr, N); // This code is contributed by SoumikMondal> PHP // Php program for implementation of Heap Sort // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap function heapify(&$arr, $N, $i) { $largest = $i; // Initialize largest as root $l = 2*$i + 1; // left = 2*i + 1 $r = 2*$i + 2; // right = 2*i + 2 // If left child is larger than root if ($l < $N && $arr[$l]>$arr[$largest]) $largest = $l; // 오른쪽 자식이 지금까지 가장 큰 것보다 큰 경우 if ($r< $N && $arr[$r]>$arr[$largest]) $largest = $r; // maximum이 루트가 아닌 경우 if ($largest != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$largest]; $arr[$largest] = $스왑; // 영향을 받은 하위 트리를 반복적으로 힙화합니다. heapify($arr, $N, $largest); } } // 힙 정렬을 수행하는 주요 함수 function heapSort(&$arr, $N) { // 힙 구축(배열 재정렬) for ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // 힙에서 요소를 하나씩 추출합니다. for ($i = $N-1; $i> 0; $i--) { // 현재 루트를 끝으로 이동 $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $온도; // 감소된 힙에서 최대 heapify를 호출합니다. heapify($arr, $i, 0); } } /* n 크기의 배열을 인쇄하는 유틸리티 함수 */ function printArray(&$arr, $N) { for ($i = 0; $i< $N; ++$i) echo ($arr[$i].' ') ; } // Driver's program $arr = array(12, 11, 13, 5, 6, 7); $N = sizeof($arr)/sizeof($arr[0]); // Function call heapSort($arr, $N); echo 'Sorted array is ' . '
'; printArray($arr , $N); // This code is contributed by Shivi_Aggarwal ?>> 파이썬3 # Python program for implementation of heap Sort # To heapify subtree rooted at index i. # n is size of heap def heapify(arr, N, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # See if left child of root exists and is # greater than root if l < N and arr[largest] < arr[l]: largest = l # See if right child of root exists and is # greater than root if r < N and arr[largest] < arr[r]: largest = r # Change root, if needed if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # swap # Heapify the root. heapify(arr, N, largest) # The main function to sort an array of given size def heapSort(arr): N = len(arr) # Build a maxheap. for i in range(N//2 - 1, -1, -1): heapify(arr, N, i) # One by one extract elements for i in range(N-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # swap heapify(arr, i, 0) # Driver's code if __name__ == '__main__': arr = [12, 11, 13, 5, 6, 7] # Function call heapSort(arr) N = len(arr) print('Sorted array is') for i in range(N): print('%d' % arr[i], end=' ') # This code is contributed by Mohit Kumra> 산출
Sorted array is 5 6 7 11 12 13>
복잡성 분석 힙 정렬
시간 복잡도: O(N로그N)
보조 공간: 재귀 호출 스택으로 인해 O(log n)입니다. 그러나 반복 구현을 위해 보조 공간은 O(1)이 될 수 있습니다.
힙 정렬에 대한 중요 사항:
- 힙 정렬은 내부 알고리즘입니다.
- 일반적인 구현은 안정적이지는 않지만 안정적으로 만들 수 있습니다(참조 이것 )
- 일반적으로 잘 구현된 것보다 2~3배 느림 퀵정렬 . 속도가 느려지는 이유는 참조 지역성이 부족하기 때문입니다.
힙 정렬의 장점:
- 효율적인 시간 복잡도: 힙 정렬은 모든 경우에 O(n log n)의 시간 복잡도를 갖습니다. 이는 대규모 데이터 세트를 정렬하는 데 효율적입니다. 그만큼 로그 n 요소는 바이너리 힙의 높이에서 나오며, 요소 수가 많아도 알고리즘이 좋은 성능을 유지하도록 보장합니다.
- 메모리 사용량 – (재귀적 heapify() 대신 반복적 heapify()를 작성하여) 메모리 사용량을 최소화할 수 있습니다. 따라서 정렬할 항목의 초기 목록을 보관하는 데 필요한 것 외에는 작업을 위해 추가 메모리 공간이 필요하지 않습니다.
- 단순성 – 재귀와 같은 고급 컴퓨터 과학 개념을 사용하지 않기 때문에 동일하게 효율적인 다른 정렬 알고리즘보다 이해하기가 더 쉽습니다.
힙 정렬의 단점:
- 비용이 많이 든다 : 힙 정렬은 시간 복잡도가 O(n Log n)인 경우에도 병합 정렬에 비해 상수가 높기 때문에 비용이 많이 듭니다.
- 불안정한 : 힙 정렬이 불안정합니다. 상대 순서를 다시 정렬할 수도 있습니다.
- 효율적인: 힙 정렬은 매우 복잡한 데이터를 작업할 때 그다지 효율적이지 않습니다.
힙 정렬과 관련된 자주 묻는 질문
Q1. 힙 정렬의 두 단계는 무엇입니까?
힙 정렬 알고리즘은 두 단계로 구성됩니다. 첫 번째 단계에서는 배열이 최대 힙으로 변환됩니다. 두 번째 단계에서는 가장 높은 요소(즉, 트리 루트에 있는 요소)가 제거되고 나머지 요소는 새로운 최대 힙을 만드는 데 사용됩니다.
Q2. 힙 정렬이 안정적이지 않은 이유는 무엇입니까?
힙 정렬 알고리즘은 heapSort()에서 arr[i]를 arr[0]으로 바꾸므로 동등한 키의 상대적 순서가 변경될 수 있으므로 안정적인 알고리즘이 아닙니다.
메소드 java와 같음
Q3. 힙 정렬(Heap Sort)은 분할 정복(Divide and Conquer) 알고리즘의 예입니까?
힙 정렬은 아니다 전혀 분할 및 정복 알고리즘입니다. 요소를 정렬하기 위한 분할 및 정복 접근 방식이 아닌 힙 데이터 구조를 사용하여 해당 요소를 효율적으로 정렬합니다.
Q4. 힙 정렬과 병합 정렬 중 어떤 정렬 알고리즘이 더 좋나요?
대답은 시간 복잡성과 공간 요구 사항을 비교하는 데 있습니다. 병합 정렬은 힙 정렬보다 약간 빠릅니다. 그러나 병합 정렬에는 추가 메모리가 필요합니다. 요구 사항에 따라 어떤 것을 사용할지 선택해야 합니다.
Q5. 힙 정렬이 선택 정렬보다 나은 이유는 무엇입니까?
힙 정렬은 선택 정렬과 유사하지만 최대 요소를 얻는 더 나은 방법이 있습니다. 일정한 시간에 최대 요소를 얻기 위해 힙 데이터 구조를 활용합니다.