heap sort c with examples
예제를 사용한 힙 정렬 소개.
힙 정렬은 가장 효율적인 정렬 기술 중 하나입니다. 이 기술은 지정된 정렬되지 않은 배열에서 힙을 빌드 한 다음 힙을 다시 사용하여 배열을 정렬합니다.
Heapsort는 비교를 기반으로하는 정렬 기술이며 이진 힙을 사용합니다.
배열 자바에서 값을 제거하는 방법
학습 내용 :
바이너리 힙이란?
바이너리 힙은 완전한 바이너리 트리를 사용하여 표현됩니다. 완전한 이진 트리는 리프 노드를 제외하고 각 수준의 모든 노드가 완전히 채워지고 노드가 가장 왼쪽에있는 이진 트리입니다.
바이너리 힙 또는 단순히 힙은 루트 노드가 두 개의 자식 노드보다 큰 방식으로 항목 또는 노드가 저장되는 완전한 바이너리 트리입니다. 이를 최대 힙이라고도합니다.
바이너리 힙의 항목은 루트 노드가 두 개의 하위 노드보다 작은 최소 힙으로 저장할 수도 있습니다. 힙을 이진 트리 또는 배열로 나타낼 수 있습니다.
힙을 배열로 나타내면서 인덱스가 0에서 시작한다고 가정하면 루트 요소는 0에 저장됩니다. 일반적으로 부모 노드가 I 위치에 있으면 왼쪽 자식 노드가 위치 (2 * I + 1) 오른쪽 노드는 (2 * I +2)에 있습니다.
일반 알고리즘
다음은 힙 정렬 기술에 대한 일반적인 알고리즘입니다.
- 루트가 힙의 가장 높은 요소가되도록 주어진 데이터에서 최대 힙을 빌드하십시오.
- 루트, 즉 힙에서 가장 높은 요소를 제거하고 힙의 마지막 요소로 바꾸거나 교체합니다.
- 그런 다음 최대 힙 속성 (heapify)을 위반하지 않도록 최대 힙을 조정합니다.
- 위의 단계는 힙 크기를 1만큼 줄입니다.
- 힙 크기가 1로 줄어들 때까지 위의 세 단계를 반복하십시오.
주어진 데이터 세트를 오름차순으로 정렬하는 일반 알고리즘에서 볼 수 있듯이 먼저 주어진 데이터에 대해 최대 힙을 구성합니다.
다음 데이터 세트로 최대 힙을 구성하는 예를 들어 보겠습니다.
6, 10, 2, 4, 1
이 데이터 세트에 대한 트리를 다음과 같이 구성 할 수 있습니다.
위의 트리 표현에서 괄호 안의 숫자는 배열의 각 위치를 나타냅니다.
위 표현의 최대 힙을 구성하려면 부모 노드가 자식 노드보다 커야한다는 힙 조건을 충족해야합니다. 즉, 트리를 최대 힙으로 변환하려면 트리를 'heapify'해야합니다.
위의 트리를 힙화 한 후 아래와 같이 최대 힙을 얻습니다.
위와 같이 어레이에서 생성 된이 최대 힙이 있습니다.
다음으로 힙 정렬을 보여줍니다. max-heap의 구성을 확인 했으므로 max-heap을 구성하는 세부 단계를 건너 뛰고 각 단계에서 최대 힙을 직접 표시합니다.
삽화
다음 요소 배열을 고려하십시오. 힙 정렬 기술을 사용하여이 배열을 정렬해야합니다.
정렬 할 배열에 대해 아래와 같이 최대 힙을 구성 해 보겠습니다.
Eclipse에서 Java 프로젝트를 만드는 방법
힙이 생성되면 아래와 같이 배열 형태로 표현합니다.
이제 우리는 1을 비교합니다성노드 (루트)를 마지막 노드로 바꾼 다음 교체합니다. 따라서 위와 같이 17과 3을 교체하여 17이 마지막 위치에 있고 3이 첫 번째 위치에 있도록합니다.
이제 힙에서 노드 17을 제거하고 아래 음영 부분에 표시된대로 정렬 된 배열에 넣습니다.
이제 배열 요소에 대한 힙을 다시 구성합니다. 이번에는 힙에서 하나의 요소 (17)를 삭제 했으므로 힙 크기가 1만큼 줄어 듭니다.
나머지 요소의 힙은 다음과 같습니다.
다음 단계에서 동일한 단계를 반복합니다.
힙의 루트 요소와 마지막 요소를 비교하고 교체합니다.
스왑 후 힙에서 요소 12를 삭제하고 정렬 된 배열로 이동합니다.
다시 한번 아래와 같이 나머지 요소에 대해 최대 힙을 구성합니다.
이제 루트와 마지막 요소, 즉 9와 3을 스왑합니다. 스왑 후 요소 9는 힙에서 삭제되고 정렬 된 배열에 배치됩니다.
이 시점에서는 아래와 같이 힙에 3 개의 요소 만 있습니다.
6과 3을 바꾸고 힙에서 요소 6을 삭제하고 정렬 된 배열에 추가합니다.
이제 나머지 요소의 힙을 구성한 다음 둘 다 서로 교체합니다.
4와 3을 바꾼 후 힙에서 요소 4를 삭제하고 정렬 된 배열에 추가합니다. 이제 아래와 같이 힙에 하나의 노드 만 남아 있습니다. .
이제 하나의 노드 만 남아 있으므로 힙에서 삭제하고 정렬 된 배열에 추가합니다.
따라서 위에 표시된 것은 힙 정렬의 결과로 얻은 정렬 된 배열입니다.
위의 그림에서는 배열을 오름차순으로 정렬했습니다. 배열을 내림차순으로 정렬해야하는 경우 동일한 단계를 수행해야하지만 최소 힙을 사용해야합니다.
힙 정렬 알고리즘은 가장 작은 요소를 선택하여 정렬 된 배열에 배치하는 선택 정렬과 동일합니다. 그러나 힙 정렬은 성능면에서 선택 정렬보다 빠릅니다. heapsort는 선택 정렬의 개선 된 버전이기 때문에 우리는 그것을 넣을 수 있습니다.
다음으로 C ++ 및 Java 언어로 Heapsort를 구현합니다.
두 구현에서 가장 중요한 기능은 'heapify'기능입니다. 이 함수는 노드가 삭제되거나 max-heap이 빌드 될 때 하위 트리를 재정렬하기 위해 기본 힙 정렬 루틴에 의해 호출됩니다.
트리를 올바르게 힙화하면 올바른 위치에서 올바른 요소를 얻을 수 있으므로 배열이 올바르게 정렬됩니다.
C ++ 예
다음은 힙 정렬 구현을위한 C ++ 코드입니다.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i 산출:
입력 배열
4 17 3 12 9 6
정렬 된 배열
34 6 9 12 17
다음으로 자바 언어로 힙 정렬을 구현합니다.
자바 예
// Java program to implement Heap Sort class HeapSort { public void heap_sort(int arr()) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // heapify the sub-tree void heapify(int arr(), int n, int root) { int largest = root; // Initialize largest as root int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { int swap = arr(root); arr(root) = arr(largest); arr(largest) = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } //print array contents - utility function static void displayArray(int arr()) { int n = arr.length; for (int i=0; i 산출:
입력 배열 :
4 17 3 12 9 6
정렬 된 배열 :
34 6 9 12 17
기본 HTML 및 CSS 인터뷰 질문
결론
Heapsort는 바이너리 힙을 사용하는 비교 기반 정렬 기술입니다.
이러한 정렬 기술은 배열에서 가장 큰 요소 또는 가장 작은 요소를 반복적으로 찾은 다음 정렬 된 배열에 배치하는 유사한 논리로 작동하기 때문에 선택 정렬보다 개선이라고 할 수 있습니다.
힙 정렬은 max-heap 또는 min-heap을 사용하여 배열을 정렬합니다. 힙 정렬의 첫 번째 단계는 배열 데이터에서 최소 또는 최대 힙을 빌드 한 다음 루트 요소를 재귀 적으로 삭제하고 힙에 노드가 하나만있을 때까지 힙을 힙화하는 것입니다.
힙 정렬은 효율적인 알고리즘이며 선택 정렬보다 빠르게 수행됩니다. 거의 정렬 된 배열을 정렬하거나 배열에서 k 개의 가장 크거나 가장 작은 요소를 찾는 데 사용할 수 있습니다.
이것으로 C ++의 정렬 기술에 대한 주제를 완료했습니다. 다음 튜토리얼부터는 데이터 구조를 하나씩 시작하겠습니다.
=> 여기에서 전체 C ++ 교육 시리즈를 찾아보십시오.
추천 도서