힙 정렬 알고리즘(코드 포함) Python and C++)
사라 첸
힙 정렬 알고리즘이란 무엇입니까?
힙 정렬은 인기 있고 빠른 정렬 알고리즘 중 하나입니다. 완전한 이진 트리 데이터 구조에 기반합니다. 최대 요소를 검색하여 최대 힙의 맨 위에 놓습니다. 이진 트리의 부모 노드에 놓습니다.
배열이 주어졌다고 가정해 보겠습니다. 데이터 = [10,5, 7, 9, 4, 11, 45, 17, 60].
배열에서 i번째 (i=0,1,2,3 …) 인덱스가 부모 노드이면 (2i+1)과 (2i+2)가 왼쪽 및 오른쪽 자식이 됩니다. 이 배열을 사용하여 완전한 이진 트리를 생성하면 다음과 같습니다.
우리는 배열의 처음부터 끝까지 heapify 프로세스를 수행할 것입니다. 처음에 배열을 트리로 변환하면 위와 같이 보일 것입니다. 우리는 그것이 어떠한 heap 속성(최소 heap 또는 최대 heap)도 유지하지 않는다는 것을 알 수 있습니다. 우리는 모든 노드에 대해 heapify 프로세스를 수행하여 정렬된 배열을 얻을 것입니다.
힙 정렬의 적용
힙 정렬 알고리즘의 사용법은 다음과 같습니다.
- "우선순위 큐"를 구성하려면 힙 정렬이 필요합니다. heapsort는 각 삽입이 이루어진 후에 요소를 정렬된 상태로 유지하기 때문입니다.
- 힙 데이터 구조는 k를 찾는 데 효율적입니다.th 주어진 배열에서 가장 큰 요소입니다.
- Linux 커널은 힙 정렬을 기본값으로 사용합니다. 정렬 알고리즘 그것은 O(1)의 공간 복잡도를 가지고 있습니다.
예제를 사용하여 힙 정렬 만들기
여기서는 다음의 완전 이진 트리에서 최대 힙을 구성합니다.
리프 노드는 17, 60, 4, 11, 45입니다. 자식 노드가 없습니다. 그래서 리프 노드입니다. 따라서 부모 노드에서 heapify 메서드를 시작합니다. 단계는 다음과 같습니다.
단계 1) 가장 왼쪽의 하위 트리를 선택합니다. 하위 노드가 더 크면 상위 노드를 하위 노드로 바꿉니다.
여기서 상위 노드는 9입니다. 하위 노드는 17과 60입니다. 60이 가장 크므로 60과 9를 교체하여 최대 힙.
단계 2) 이제 가장 왼쪽 하위 트리가 힙화됩니다. 다음 상위 노드는 7입니다. 이 상위 노드에는 두 개의 하위 노드가 있으며 가장 큰 노드는 45입니다. 따라서 45와 7이 교체됩니다.
단계 3) 노드 60과 4에는 상위 노드 5가 있습니다. "5"는 하위 노드 60보다 작으므로 교체됩니다.
단계 4) 이제 노드 5에는 하위 노드 17,9가 있습니다. 이는 최대 힙 속성을 유지하지 않습니다. 따라서 5는 17로 대체됩니다.
단계 5) 노드 10은 60과 교환되고, 그다음 17과 교환됩니다. 이 과정은 다음과 같습니다.
단계 6) 5단계까지는 최대 힙을 생성했습니다. 모든 상위 노드는 하위 노드보다 큽니다. 루트 노드의 최대값은 60입니다.
참고 : 정렬된 배열을 생성하려면 최대값 노드를 후속 노드로 바꿔야 합니다.
이 과정을 "최대 추출". 60이 최대 노드이므로 위치를 0번째 인덱스로 고정하고 노드 60 없이 힙을 생성합니다.
단계 7) 60이 제거되면 다음 최대값은 45입니다. 노드 45에서 "Extract Max" 프로세스를 다시 수행합니다.
이번에는 45를 얻고 루트 노드를 후속 노드 17로 교체합니다.
우리는 "최대 추출” 모든 요소가 정렬될 때까지.
이러한 단계를 반복하여 모든 최대값을 추출하면 다음 배열을 얻게 됩니다.
바이너리 힙이란 무엇입니까?
바이너리 힙은 일종의 완전한 힙입니다. 이진 트리 데이터 구조. 이러한 종류의 트리 구조에서 상위 노드는 하위 노드보다 크거나 작습니다. 상위 노드가 더 작으면 힙을 "최소 힙"이라고 하고, 상위 노드가 더 크면 힙을 "최대 힙"이라고 합니다.
다음은 최소 힙과 최대 힙의 예입니다.
위 그림에서 "최소 힙"이 보이면 상위 노드는 항상 하위 노드보다 작습니다. 트리의 머리 부분에서 가장 작은 값인 10을 찾을 수 있습니다.
마찬가지로 "최대 힙"의 경우 상위 노드는 항상 하위 노드보다 큽니다. 최대 요소는 "최대 힙"의 헤드 노드에 있습니다.
"Heapify"란 무엇입니까?
"Heapify"는 노드의 위치를 보장하는 힙의 원리입니다. Heapify에서 최대 힙은 항상 부모와 자식과의 관계를 유지하며, 즉 부모 노드는 자식 노드보다 더 큽니다.
예를 들어, 새로운 노드가 추가되면 힙을 리셰이핑해야 합니다. 그러나 노드를 변경하거나 스왑하거나 배열을 재정렬해야 할 수도 있습니다. 힙을 리셰이핑하는 이 프로세스를 "heapify"라고 합니다.
다음은 heapify가 작동하는 방식의 예입니다.
heapify의 단계는 다음과 같습니다.
단계 1) 노드 65의 오른쪽 하위 항목으로 노드 60를 추가했습니다.
단계 2) 새로 추가된 노드가 상위 노드보다 큰지 확인하세요.
단계 3) 부모 노드보다 크기 때문에 올바른 자식을 부모 노드로 교체했습니다.
힙을 구축하는 방법
힙을 구축하거나 트리를 힙화하기 전에 우리는 그것을 어떻게 저장할지 알아야 합니다. 힙은 완전 이진 트리이므로 다음을 사용하는 것이 좋습니다. 정렬 힙의 데이터를 보유합니다.
배열에 총 n개의 요소가 포함되어 있다고 가정해 보겠습니다. "i"번째 인덱스가 부모 노드인 경우 왼쪽 노드는 인덱스에 위치합니다. (2i+1), 그리고 오른쪽 노드는 인덱스에 있을 것입니다 (2i+2). 배열 인덱스는 0부터 시작한다고 가정합니다.
이것을 사용하여 다음과 같이 배열과 같은 최대 힙을 저장해 보겠습니다.
heapify 알고리즘은 heap 속성을 유지합니다. 부모 노드에 극단적인 값(작거나 큰 값)이 없으면 가장 극단적인 자식 노드와 교환됩니다.
최대 힙을 힙화하는 단계는 다음과 같습니다.
단계 1) 리프 노드에서 시작합니다.
단계 2) 부모와 자식 사이의 최대값을 찾아보세요.
단계 3) 하위 노드의 값이 상위 노드보다 큰 경우 노드를 교환합니다.
단계 4) 한 레벨 위로 이동하세요.
단계 5) 인덱스 2,3,4에 도달하거나 전체 트리를 정렬할 때까지 0단계를 따르세요.
재귀적 힙화(최대 힙)에 대한 의사 코드는 다음과 같습니다.
def heapify(): input→ array, size, i largest = i left = 2*i + 1 right = 2*i + 2 if left<n and array[largest ] < array[left]: largest = left if right<n and array[largest ] < array[right]: largest = right If largest not equals i: swap(array[i],array[largest]) heapify(array,n,largest)
힙 정렬을 위한 의사 코드
힙 정렬 알고리즘에 대한 의사 코드는 다음과 같습니다.
Heapify(numbers as an array, n as integer, i as integer): largest = i left = 2i+1 right= 2i+2 if(left<=n) and (numbers[i]<numbers[left]) largest=left if(right<=n) and (numbers[i]<numbers[right]) largest=right if(largest != i) swap(numbers[i], numbers[largest]) Heapify(numbers,n,largest) HeapSort(numbers as an array): n= numbers.size() for i in range n/2 to 1 Heapify(numbers,n,i) for i in range n to 2 Swap numbers[i] with numbers[1] Heapify(numbers,i,0)
힙 정렬 코드의 예 C++
#include <iostream>
using namespace std;
void display(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
void heapify(int numbers[], int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && numbers[left] < numbers[largest])
{
largest = left;
}
if (right < n && numbers[right] < numbers[largest])
{
largest = right;
}
if (largest != i)
{
//uncomment the following line to see details in output
//cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
swap(numbers[i], numbers[largest]);
heapify(numbers, n, largest);
}
}
void heapSort(int numbers[], int n)
{
for (int i = n/2 - 1; i >= 0; i--)
{
heapify(numbers, n, i);
//uncomment the following line to see details in output
//cout<<"Heapify:\t";
//display(numbers,n);
}
for (int i = n - 1; i >= 0; i--)
{
swap(numbers[0], numbers[i]);
heapify(numbers, i, 0);
}
}
int main()
{
int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
int size = sizeof(numbers) / sizeof(numbers[0]);
cout<<"Initial Array:\t";
display(numbers,size);
heapSort(numbers, size);
cout<<"Sorted Array (descending order):\t";
display(numbers, size);
}
출력:
Initial Array: 10 5 7 9 4 11 45 17 60 Sorted Array (descending order): 60 45 17 11 10 9 7 5 4
힙 정렬 코드의 예 Python
def display(arr):
for i in range(len(arr)):
print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
largest = left
if right < n and numbers[right] < numbers[largest]:
largest = right
if largest != i:
numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
for i in range(n //2,-1,-1):
heapify(items, n, i) for i in range(n - 1, -1, -1):
items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)
출력:
Initial List: 10 5 7 9 4 11 45 17 60 After HeapSort: 60 45 17 11 10 9 7 5 4
Heap Sort의 시간 및 공간 복잡도 분석
힙 정렬에 대해 분석할 수 있는 시간 복잡도와 공간 복잡도가 있습니다. 시간 복잡도의 경우 다음과 같은 경우가 있습니다.
- 최상의 사례
- 평균 케이스
- 최악의 경우
힙은 완전한 이진 트리에서 구현됩니다. 따라서 이진 트리의 최하위 수준에는 최대 노드 수가 있습니다. 맨 아래 수준에 n개의 노드가 있으면 위 수준에는 n/2개의 노드가 있습니다.
이 예에서 수준 3에는 2개의 항목이 있고 수준 1에는 XNUMX개의 항목이 있으며 수준 XNUMX에는 XNUMX개의 항목이 있습니다. 총 n개의 아이템이 있을 경우, 높이 또는 총 레벨은 다음과 같습니다. 로그2(N). 따라서 단일 요소를 삽입하려면 최대 Log(n) 반복이 필요할 수 있습니다.
힙에서 최대값을 가져오고 싶을 때는 루트 노드만 가져옵니다. 그런 다음 다시 heapify를 실행합니다. 각 heapify는 로그2(엔) 시간. 최대값을 추출하는 데는 O(1) 시간이 걸립니다.
힙 정렬 알고리즘의 최적 케이스 시간 복잡도
모든 요소가 이미 배열에 정렬되어 있으면 힙을 만드는 데 O(n) 시간이 걸립니다. 목록이 정렬된 경우 항목을 삽입하는 데 O(1)이라는 일정한 시간이 걸리기 때문입니다.
따라서 최선의 경우 최대 힙 또는 최소 힙을 생성하는 데 O(n) 시간이 걸립니다.
힙 정렬 알고리즘의 평균 케이스 시간 복잡도
항목을 삽입하거나 최대값을 추출하는 데는 O(log(n)) 시간이 소요됩니다. 따라서 힙 정렬 알고리즘의 평균 케이스 시간 복잡도는 다음과 같습니다. O(n로그(n)).
힙 정렬 알고리즘의 최악의 경우 시간 복잡도
평균적인 경우와 유사하게 최악의 경우 시나리오에서 우리는 heapify를 n번 수행할 수 있습니다. 각 heapify는 O(log(n)) 시간이 소요됩니다. 따라서 최악의 경우 시간 복잡도는 다음과 같습니다. O(n로그(n)).
힙 정렬 알고리즘의 공간 복잡도
힙 정렬은 제자리에서 설계된 알고리즘입니다. 즉, 작업을 수행하는 데 추가 또는 임시 메모리가 필요하지 않습니다. 구현을 보면 노드 교환을 수행하기 위해 swap()을 사용했음을 알 수 있습니다. 다른 목록이나 배열은 필요하지 않습니다. 따라서 공간 복잡도는 O(1)입니다.
