힙 정렬 알고리즘(Python 및 C++ 코드 사용)

힙 정렬 알고리즘이란 무엇입니까?

힙 정렬(Heap Sort)은 인기 있고 빠른 정렬 알고리즘 중 하나입니다. 이는 완전한 이진 트리 데이터 구조를 기반으로 구축되었습니다. 최대 요소를 검색하여 최대 힙의 맨 위에 배치합니다. 우리는 그것을 이진 트리의 부모 노드에 놓을 것입니다.

배열이 주어졌다고 가정해 보겠습니다. 데이터 = [10,5, 7, 9, 4, 11, 45, 17, 60].

배열에서 i번째 (i=0,1,2,3 …) 인덱스가 부모 노드이면 (2i+1)과 (2i+2)가 왼쪽 및 오른쪽 자식이 됩니다. 이 배열을 사용하여 완전한 이진 트리를 생성하면 다음과 같습니다.

힙 정렬 알고리즘

배열의 처음부터 끝까지 heapify 프로세스를 수행합니다. 처음에 배열을 트리로 변환하면 위와 같은 모습이 됩니다. 힙 속성(최소 힙 또는 최대 힙)을 유지하지 않는 것을 볼 수 있습니다. 모든 노드에 대해 heapify 프로세스를 수행하여 정렬된 배열을 얻습니다.

힙 정렬의 적용

힙 정렬 알고리즘의 사용법은 다음과 같습니다.

  • "우선순위 큐"를 구성하려면 힙 정렬이 필요합니다. heapsort는 각 삽입이 이루어진 후에 요소를 정렬된 상태로 유지하기 때문입니다.
  • 힙 데이터 구조는 k를 찾는 데 효율적입니다.th 주어진 배열에서 가장 큰 요소입니다.
  • Linux 커널은 힙 정렬을 기본값으로 사용합니다. 정렬 알고리즘 O(1)개의 space com이 있으므로plexity.

예제를 사용하여 힙 정렬 만들기

여기서는 follo에서 최대 힙을 구성합니다.wing 완전한 이진 트리.

예제를 사용하여 힙 정렬 만들기

리프 노드는 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로 교체됩니다. 프로세스는 다음과 같습니다.wing.

예제를 사용하여 힙 정렬 만들기

예제를 사용하여 힙 정렬 만들기

단계 6) 5단계까지는 최대 힙을 생성했습니다. 모든 상위 노드는 하위 노드보다 큽니다. 루트 노드의 최대값은 60입니다.

참고 : 정렬된 배열을 생성하려면 최대값 노드를 후속 노드로 바꿔야 합니다.

이 과정을 "최대 추출". 60이 최대 노드이므로 위치를 0번째 인덱스로 고정하고 노드 60 없이 힙을 생성합니다.

예제를 사용하여 힙 정렬 만들기

예제를 사용하여 힙 정렬 만들기

단계 7) 60이 제거되면 다음 최대값은 45입니다. 노드 45에서 "Extract Max" 프로세스를 다시 수행합니다.

이번에는 45를 얻고 루트 노드를 후속 노드 17로 교체합니다.

우리는 "최대 추출” 모든 요소가 정렬될 때까지.

모든 최대값을 추출할 때까지 이러한 단계를 수행한 후 다음과 같은 결과를 얻게 됩니다.wing 정렬.

예제를 사용하여 힙 정렬 만들기

바이너리 힙이란 무엇입니까?

바이너리 힙은 일종의 완전한 힙입니다. 이진 트리 데이터 구조. 이러한 종류의 트리 구조에서 상위 노드는 하위 노드보다 크거나 작습니다. 상위 노드가 더 작으면 힙을 "최소 힙"이라고 하고, 상위 노드가 더 크면 힙을 "최대 힙"이라고 합니다.

다음은 최소 힙과 최대 힙의 예입니다.

최소 힙 및 최대 힙
최소 힙 및 최대 힙

위 그림에서 "최소 힙"이 보이면 상위 노드는 항상 하위 노드보다 작습니다. 트리의 머리 부분에서 가장 작은 값인 10을 찾을 수 있습니다.

마찬가지로 "최대 힙"의 경우 상위 노드는 항상 하위 노드보다 큽니다. 최대 요소는 "최대 힙"의 헤드 노드에 있습니다.

"힙파이"란 무엇인가요?

"Heapify"는 노드의 위치를 ​​보장하는 힙의 원리입니다. Heapify에서 최대 힙은 항상 상위 및 하위 관계를 유지하며, 즉 상위 노드가 하위 노드보다 커집니다.

예를 들어 새 노드가 추가되면 힙의 모양을 변경해야 합니다. 그러나 노드를 변경 또는 교체하거나 어레이를 재배열해야 할 수도 있습니다. 힙을 재구성하는 이러한 프로세스를 "힙화"라고 합니다.

다음은 heapify 작동 방식의 예입니다.

새 노드 추가 및 Heapify
새 노드 추가 및 힙화

Heapify의 단계는 다음과 같습니다.

단계 1) 노드 65의 오른쪽 하위 항목으로 노드 60를 추가했습니다.

단계 2) 새로 추가된 노드가 상위 노드보다 큰지 확인하세요.

단계 3) 부모 노드보다 크기 때문에 올바른 자식을 부모 노드로 교체했습니다.

힙을 구축하는 방법

힙을 쌓거나 트리를 쌓기 전에 이를 어떻게 저장할지 알아야 합니다. 힙은 완전한 이진 트리이므로 다음을 사용하는 것이 좋습니다. 정렬 힙의 데이터를 보유합니다.

배열에 총 n개의 요소가 포함되어 있다고 가정해 보겠습니다. "i"번째 인덱스가 부모 노드인 경우 왼쪽 노드는 인덱스에 위치합니다. (2i+1), 그리고 오른쪽 노드는 인덱스에 있을 것입니다 (2i+2). 배열 인덱스는 0부터 시작한다고 가정합니다.

이것을 사용하여 배열과 같은 follo에 최대 힙을 저장해 보겠습니다.wing:

최대 힙의 배열 기반 표현
최대 힙의 배열 기반 표현

heapify 알고리즘은 힙 속성을 유지합니다. 상위 노드에 극한값(더 작거나 큼)이 없으면 가장 극단적인 하위 노드로 교체됩니다.

최대 힙을 힙화하는 단계는 다음과 같습니다.

단계 1) 리프 노드에서 시작합니다.

단계 2) 부모와 자식 사이의 최대값을 찾아보세요.

단계 3) 하위 노드의 값이 상위 노드보다 큰 경우 노드를 교환합니다.

단계 4) 한 레벨 위로 이동하세요.

단계 5) 인덱스 2,3,4에 도달하거나 전체 트리를 정렬할 때까지 0단계를 따르세요.

재귀적 heapify(최대 힙)에 대한 의사 코드는 다음과 같습니다.

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

타임앤스페이스컴plex힙 정렬의 특성 분석

시간이 있어요 complexity 및 Space complex힙 정렬을 분석할 수 있는 것입니다. 타임컴용plex우리가 그 사람이야wing 사례 :

  1. 최상의 사례
  2. 평균 케이스
  3. 최악의 경우

힙은 완전한 이진 트리에서 구현됩니다. 따라서 이진 트리의 최하위 수준에는 최대 노드 수가 있습니다. 맨 아래 수준에 n개의 노드가 있으면 위 수준에는 n/2개의 노드가 있습니다.

타임앤스페이스컴plex성 분석

이 예에서 수준 3에는 2개의 항목이 있고 수준 1에는 XNUMX개의 항목이 있으며 수준 XNUMX에는 XNUMX개의 항목이 있습니다. 총 n개의 아이템이 있을 경우, 높이 또는 총 레벨은 다음과 같습니다. 로그2(N). 따라서 단일 요소를 삽입하려면 최대 Log(n) 반복이 필요할 수 있습니다.

힙에서 최대값을 가져오려면 루트 노드만 가져옵니다. 그런 다음 다시 heapify를 실행하십시오. 각 힙파이에는 로그2(엔) 시간. 최대값을 추출하는 데는 O(1) 시간이 걸립니다.

베스트 케이스 타임컴plex힙 정렬 알고리즘에 대한 ity

모든 요소가 이미 배열에 정렬되어 있으면 힙을 만드는 데 O(n) 시간이 걸립니다. 목록이 정렬된 경우 항목을 삽입하는 데 O(1)이라는 일정한 시간이 걸리기 때문입니다.

따라서 최선의 경우 최대 힙 또는 최소 힙을 생성하는 데 O(n) 시간이 걸립니다.

평균 케이스 시간 통신plex힙 정렬 알고리즘에 대한 ity

항목을 삽입하거나 최대값을 추출하는 데는 O(log(n)) 시간이 소요됩니다. 따라서 평균 케이스 시간은 complex힙 정렬 알고리즘의 특성은 다음과 같습니다. O(n로그(n)).

최악의 경우 시간 통신plex힙 정렬 알고리즘에 대한 ity

평균적인 경우와 유사하게 최악의 시나리오에서는 heapify를 n번 수행해야 할 수도 있습니다. 각 힙화에는 O(log(n)) 시간이 소요됩니다. 그래서 최악의 경우는 타임컴plex이 될 것입니다 O(n로그(n)).

스페이스컴plex힙 정렬 알고리즘에 대한 ity

힙 정렬은 내부 설계 알고리즘입니다. 이는 작업을 수행하는 데 추가 또는 임시 메모리가 필요하지 않음을 의미합니다. 구현을 보면 노드 교환을 수행하기 위해 swap()을 사용했음을 알 수 있습니다. 다른 목록이나 배열은 필요하지 않았습니다. 그래서 스페이스컴은plexity는 O(1)입니다.