힙 정렬

1. 힙 정렬 알고리즘
2. 힙 정렬 예
3. 힙 정렬 알고리즘 구현
4. 힙 정렬 알고리즘 복잡성

힙 정렬은 비교 기반 정렬 알고리즘입니다. 알고리즘에 사용 된 힙 데이터 구조에서 이름을 가져옵니다. 힙은 이진 트리 기반 특수 데이터 구조입니다. 다음과 같은 두 가지 속성이 있습니다.

• 마지막 레벨을 제외한 모든 레벨이 채워진 완전한 이진 트리입니다. 마지막 노드는 부분적으로 채워질 수 있지만 모든 노드는 가능한 한 왼쪽에 있습니다.
• 모든 부모 노드는 두 자식 노드보다 작거나 큽니다. 더 작 으면 힙을 최소 힙이라고하고 더 크면 힙을 최대 힙이라고합니다. 주어진 인덱스i에 대해 부모는(i-1) / 2로, 왼쪽 자식은(2 * i + 1)로, 오른쪽 자식은(2 * i +2).

힙 정렬은 선택 정렬과 매우 유사한 방식으로 작동합니다. max-heap을 사용하여 배열에서 최대 요소를 선택하고 배열 뒷면의 해당 위치에 배치합니다. 힙을 빌드하기 위해heapify()라는 절차를 사용합니다.

힙 정렬 알고리즘

n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다.

HeapSort()

Heapify()

힙 정렬 예

배열이(5, 3, 4, 2, 1, 6)이라고 가정합니다. 힙 정렬 알고리즘을 사용하여 정렬합니다.

힙을 빌드 한 후 배열을(6 3 5 2 1 4)로 얻습니다.

• 첫 번째 반복 :

• 두 번째 반복 :

• 세 번째 반복 :

• 네 번째 반복 :

• 다섯 번째 반복 :

• 여섯 번째 반복 :

정렬 된 배열은(1,2,3,4,5,6)로 얻습니다.

힙 정렬 알고리즘 구현

#include <bits/stdc++.h>
using namespace std;

void heapify(int arr[], int n, int i) {
  int parent = i;
  int leftChild = 2 * i + 1;
  int rightChild = 2 * i + 2;

  if (leftChild < n && arr[leftChild] > arr[parent]) parent = leftChild;

  if (rightChild < n && arr[rightChild] > arr[parent]) parent = rightChild;

  if (parent != i) {
    swap(arr[i], arr[parent]);
    heapify(arr, n, parent);
  }
}

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(arr, i, 0);
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  heapSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

힙 정렬 알고리즘 복잡성

시간 복잡성

• 평균 사례

n 요소가있는 완전한 이진 트리의 높이는 최대logn입니다. 따라서heapify()함수는 요소가 루트에서 리프로 이동할 때 최대logn 비교를 가질 수 있습니다. 빌드 힙 함수는n/2 요소에 대해 호출되어 첫 번째 단계n/2*logn 또는T(n)=nlogn의 총 시간 복잡도를 만듭니다.

HeapSort()는 각 요소에 대해logn 최악의 시간이 걸리며n 요소는 시간 복잡도를nlogn으로 만듭니다. 힙 및 힙 정렬을 빌드하기위한 시간 복잡성이 모두 추가되어 결과 복잡성을 nlogn으로 제공합니다. 따라서 총 시간 복잡도는 [Big Theta] :O(nlogn)의 순서입니다.

• 최악의 경우

최악의 시간 복잡도는 [Big O] :O(nlogn)입니다.

• 베스트 케이스

최적의 시간 복잡도는 [Big Omega] :O(nlogn)입니다. 최악의 시간 복잡성과 동일합니다.

공간 복잡성

힙 정렬 알고리즘의 공간 복잡성은 임시 변수 이외의 추가 메모리가 필요하지 않기 때문에O(1)입니다.