힙 정렬 - DS 튜토리얼

이번 포스팅에서는 Heapsort 알고리즘에 대해 알아보겠습니다. 힙 정렬은 주어진 배열의 요소를 사용하여 최소 힙 또는 최대 힙을 생성하여 요소를 처리합니다. 최소 힙 또는 최대 힙은 루트 요소가 배열의 최소 또는 최대 요소를 나타내는 배열 순서를 나타냅니다.

힙 정렬은 기본적으로 두 가지 주요 작업을 재귀적으로 수행합니다.

배열의 요소를 사용하여 힙 H를 만듭니다.
1에서 형성된 힙의 루트 요소를 반복적으로 삭제합니다.^성단계.

힙 정렬에 대해 더 알아보기 전에 먼저 힙 정렬에 대한 간략한 설명을 살펴보겠습니다. 더미.

힙이란 무엇입니까?

힙은 완전한 이진 트리이고, 이진 트리는 노드가 최대 2개의 자식을 가질 수 있는 트리입니다. 완전 이진 트리는 마지막 수준, 즉 리프 노드를 제외한 모든 수준이 완전히 채워지고 모든 노드가 왼쪽 정렬되는 이진 트리입니다.

힙 정렬이란 무엇입니까?

Heapsort는 널리 사용되고 효율적인 정렬 알고리즘입니다. 힙 정렬의 개념은 목록의 힙 부분에서 요소를 하나씩 제거한 다음 목록의 정렬된 부분에 삽입하는 것입니다.

Heapsort는 내부 정렬 알고리즘입니다.

문자열 포맷터

이제 힙 정렬 알고리즘을 살펴보겠습니다.

연산

 HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End

BuildMaxHeap(arr)

 BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End

MaxHeapify(arr,i)

 MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] &gt; arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] &gt; arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End

힙 정렬 알고리즘의 작동

이제 Heapsort 알고리즘의 작동을 살펴보겠습니다.

힙 정렬에는 기본적으로 요소 정렬과 관련된 두 단계가 있습니다. 힙 정렬 알고리즘을 사용하면 다음과 같습니다.

첫 번째 단계에는 배열 요소를 조정하여 힙을 생성하는 작업이 포함됩니다.
힙을 생성한 후 이제 힙의 루트 요소를 배열의 끝으로 이동하여 반복적으로 제거한 다음 나머지 요소와 함께 힙 구조를 저장합니다.

이제 예제를 통해 힙 정렬 작업을 자세히 살펴보겠습니다. 더 명확하게 이해하기 위해 정렬되지 않은 배열을 선택하고 힙 정렬을 사용하여 정렬해 보겠습니다. 설명이 더 명확하고 쉬워집니다.

먼저, 주어진 배열에서 힙을 구성하고 이를 최대 힙으로 변환해야 합니다.

주어진 힙을 최대 힙으로 변환한 후 배열 요소는 다음과 같습니다.

다음으로 루트 요소를 삭제해야 합니다. (89) 최대 힙에서. 이 노드를 삭제하려면 마지막 노드와 교체해야 합니다. (열하나). 루트 요소를 삭제한 후 다시 힙화하여 최대 힙으로 변환해야 합니다.

배열 요소를 교체한 후 89 ~와 함께 열하나, 힙을 최대 힙으로 변환하면 배열 요소는 다음과 같습니다.

다음 단계에서는 다시 루트 요소를 삭제해야 합니다. (81) 최대 힙에서. 이 노드를 삭제하려면 마지막 노드와 교체해야 합니다. (54). 루트 요소를 삭제한 후 다시 힙화하여 최대 힙으로 변환해야 합니다.

배열 요소를 교체한 후 81 ~와 함께 54 힙을 최대 힙으로 변환하면 배열 요소는 다음과 같습니다.

다음 단계에서는 루트 요소를 삭제해야 합니다. (76) 다시 최대 힙에서. 이 노드를 삭제하려면 마지막 노드와 교체해야 합니다. (9). 루트 요소를 삭제한 후 다시 힙화하여 최대 힙으로 변환해야 합니다.

배열 요소를 교체한 후 76 ~와 함께 9 힙을 최대 힙으로 변환하면 배열 요소는 다음과 같습니다.

다음 단계에서는 다시 루트 요소를 삭제해야 합니다. (54) 최대 힙에서. 이 노드를 삭제하려면 마지막 노드와 교체해야 합니다. (14). 루트 요소를 삭제한 후 다시 힙화하여 최대 힙으로 변환해야 합니다.

배열 요소를 교체한 후 54 ~와 함께 14 힙을 최대 힙으로 변환하면 배열 요소는 다음과 같습니다.

다음 단계에서는 다시 루트 요소를 삭제해야 합니다. (22) 최대 힙에서. 이 노드를 삭제하려면 마지막 노드와 교체해야 합니다. (열하나). 루트 요소를 삭제한 후 다시 힙화하여 최대 힙으로 변환해야 합니다.

배열 요소를 교체한 후 22 ~와 함께 열하나 힙을 최대 힙으로 변환하면 배열 요소는 다음과 같습니다.

다음 단계에서는 다시 루트 요소를 삭제해야 합니다. (14) 최대 힙에서. 이 노드를 삭제하려면 마지막 노드와 교체해야 합니다. (9). 루트 요소를 삭제한 후 다시 힙화하여 최대 힙으로 변환해야 합니다.

배열 요소를 교체한 후 14 ~와 함께 9 힙을 최대 힙으로 변환하면 배열 요소는 다음과 같습니다.

다음 단계에서는 다시 루트 요소를 삭제해야 합니다. (열하나) 최대 힙에서. 이 노드를 삭제하려면 마지막 노드와 교체해야 합니다. (9). 루트 요소를 삭제한 후 다시 힙화하여 최대 힙으로 변환해야 합니다.

배열 요소를 교체한 후 열하나 ~와 함께 9, 배열의 요소는 -

이제 힙에는 요소가 하나만 남았습니다. 삭제하면 힙이 비어 있게 됩니다.

정렬이 완료되면 배열 요소는 다음과 같습니다.

자바의 이진 검색

이제 배열이 완전히 정렬되었습니다.

힙 정렬 복잡성

이제 최상의 경우, 평균적인 경우, 최악의 경우 힙 정렬의 시간 복잡도를 살펴보겠습니다. Heapsort의 공간 복잡도도 살펴보겠습니다.

1. 시간 복잡도

사례	시간 복잡도
최선의 경우	O(n로그)
평균 사례	O(n 로그 n)
최악의 경우	O(n 로그 n)

O(n로그).

O(n log n).

힙 정렬의 시간 복잡도는 다음과 같습니다. O(n 로그) 세 가지 경우 모두(최상의 경우, 평균 경우, 최악의 경우). n개의 요소를 갖는 완전한 이진 트리의 높이는 다음과 같습니다. 침착한.

2. 공간 복잡성

공간 복잡도	오(1)
안정적인	N0

힙 정렬의 공간 복잡도는 O(1)입니다.

힙 정렬 구현

이제 다양한 프로그래밍 언어로 된 Heap 정렬 프로그램을 살펴보겠습니다.

프로그램: C 언어로 힙 정렬을 구현하는 프로그램을 작성하세요.

 #include /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are - 
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are - 
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>