힙 정렬 시간 복잡도

힙은 '부분적으로 정렬된'이 아니라 '부분적으로 정렬된'이라고 합니다. 'sort'라는 단어는 완전한 정렬(완전한 정렬)을 의미합니다. 힙은 임의로 부분적으로 정렬되지 않습니다. 힙은 아래와 같이 기준(패턴)에 따라 부분적으로 정렬됩니다.

따라서 힙 정렬은 힙을 구축하고 힙 상단에서 정렬된 요소를 추출하는 두 단계로 구성됩니다. 두 번째 단계에서는 추출할 때마다 힙이 다시 작성됩니다. 하나의 요소가 제거된 이전 빌드에서 다시 빌드가 수행되기 때문에 각 다시 빌드는 원래 빌드 프로세스보다 빠릅니다. 이를 통해 heapsort는 완전히 정렬되지 않은 목록을 정렬합니다.

이 기사의 목적은 힙 정렬을 간략하게 설명한 다음 시간 복잡도를 생성하는 것입니다(아래 시간 복잡도의 의미 참조). 끝으로 코딩은 C++로 수행됩니다.

최소 힙

힙은 최소 힙 또는 최대 힙일 수 있습니다. 최대 힙은 첫 번째 요소가 가장 높은 요소이고 전체 트리 또는 해당 목록이 부분적으로 내림차순으로 정렬된 것입니다. 최소 힙은 첫 번째 요소가 가장 작은 요소이고 전체 목록이 부분적으로 오름차순으로 정렬된 것입니다. 이 문서에서는 최소 힙만 고려합니다. 참고: 힙 주제에서 요소는 노드라고도 합니다.

힙은 완전한 이진 트리입니다. 이진 트리는 배열(목록)로 표현할 수 있습니다. 위에서 아래로 왼쪽에서 오른쪽으로 읽습니다. 최소 힙의 힙 속성은 부모 노드가 두 자식 각각보다 작거나 같다는 것입니다. 정렬되지 않은 목록의 예는 다음과 같습니다.

이 테이블의 첫 번째 행은 배열의 요소입니다. 두 번째 행에는 0부터 시작하는 인덱스가 있습니다. 이 요소 목록은 트리로 표현할 수 있습니다. 전체 이진 트리를 만들기 위해 null 요소가 추가되었습니다. 엄밀히 말하면 null 요소는 목록(트리)의 일부가 아닙니다. 이 목록에는 순서가 없으므로 아직 힙이 아닙니다. 힙 속성에 따라 부분 순서가 있을 때 힙이 됩니다.

노드와 인덱스의 관계

힙은 힙 구성(힙 속성)을 갖기 전의 완전한 이진 트리임을 기억하십시오. 요소가 힙 속성을 따르지 않기 때문에 이전 목록은 아직 힙이 아닙니다. min-heap 속성에 따라 요소를 부분 순서로 재배열한 후 heap이 됩니다. 부분 정렬은 부분 정렬로 볼 수 있습니다(단어 '정렬'은 완전한 정렬을 의미함).

바이너리 트리가 힙이든 아니든, 각 부모는 리프(마지막) 노드를 제외하고 두 개의 자식을 가집니다. 각 부모와 자식 사이에는 인덱스 간에 수학적 관계가 있습니다. 부모가 인덱스 i에 있으면 왼쪽 자식이 인덱스에 있습니다.

오른쪽 자식은 색인에 있습니다.

이것은 0부터 시작하는 인덱싱을 위한 것입니다. 따라서 인덱스 0의 부모는 인덱스 2×0+1=1에 왼쪽 자식이 있고 2×0+2=2에 오른쪽 자식이 있습니다. 인덱스 1에 있는 부모는 인덱스 2×1+1=3에 왼쪽 자식이 있고 인덱스 2×1+2=4에 오른쪽 자식이 있습니다. 등등.

min-heap 속성에 의해 i의 부모는 2i+1에서 왼쪽 자식보다 작거나 같고 2i+2에서 오른쪽 자식보다 작거나 같습니다.

더미

힙화(heapifying)는 힙을 쌓는 것을 의미합니다. 목록(또는 해당 트리)의 요소를 힙 속성을 만족하도록 재배열하는 것을 의미합니다. 힙화 프로세스가 끝나면 목록이나 트리가 힙입니다.

이전의 정렬되지 않은 목록이 쌓이면 다음과 같이 됩니다.

참고: 목록에는 15개가 아닌 12개의 요소가 있습니다. 두 번째 행에는 인덱스가 있습니다. 힙 빌드 프로세스에서 요소를 확인하고 일부를 교체해야 했습니다.

가장 작고 첫 번째 요소는 3입니다. 나머지 요소는 오름차순이지만 기복이 있는 방식으로 따릅니다. 위치 2i+1 및 2i+2의 왼쪽 및 오른쪽 자식이 각각 i의 부모보다 크거나 같으면 최소 힙입니다. 이것은 완전한 주문이나 정렬이 아닙니다. 이것은 힙 속성에 따른 부분 순서입니다. 여기서부터 힙 정렬의 다음 단계가 시작됩니다.

시간 복잡도 증가

시간 복잡도는 일부 코드의 상대적 실행 시간입니다. 해당 코드가 완료되는 주요 작업의 수로 볼 수 있습니다. 힙 빌드를 위한 다양한 알고리즘이 있습니다. 가장 효율적이고 가장 빠른 방법은 목록을 2로 계속 나누어 맨 아래에서 요소를 확인한 다음 요소를 약간 교환하는 것입니다. N을 목록에 있는 실제 요소의 수라고 합시다. 이 알고리즘을 사용하면 주요 작업(스와핑)의 최대 수는 N입니다. 힙화를 위한 시간 복잡도는 이전에 다음과 같이 주어집니다.

여기서 n은 N이고 가능한 최대 주요 작업 수입니다. 이 표기법을 Big-O 표기법이라고 합니다. 대문자 O로 시작하고 그 뒤에 괄호가 옵니다. 괄호 안에는 가능한 최대 연산 수에 대한 표현식이 있습니다.

기억하십시오: 더해지는 것과 같은 것이 계속 반복된다면 더하기는 곱하기가 될 수 있습니다.

힙 정렬 그림

이전의 정렬되지 않은 목록은 힙 정렬을 설명하는 데 사용됩니다. 주어진 목록은 다음과 같습니다.

목록에서 생성된 최소 힙은 다음과 같습니다.

힙 정렬의 첫 번째 단계는 생성된 힙을 생성하는 것입니다. 이것은 부분적으로 정렬된 목록입니다. 정렬된(완전히 정렬된) 목록이 아닙니다.

두 번째 단계는 힙에서 첫 번째 요소인 최소 요소를 제거하고 나머지 힙을 다시 힙화하고 결과에서 가장 작은 요소를 제거하는 것으로 구성됩니다. 최소 요소는 항상 다시 쌓인 힙의 첫 번째 요소입니다. 요소는 제거되지 않고 버려집니다. 제거된 순서대로 다른 어레이로 보낼 수 있습니다.

결국 새 배열에는 모든 요소가 (완전히) 오름차순으로 정렬됩니다. 더 이상 부분적으로만 주문되지 않습니다.

두 번째 단계에서 가장 먼저 할 일은 3을 제거하고 새 배열에 배치하는 것입니다. 결과는 다음과 같습니다.

그리고

나머지 요소는 첫 번째 요소가 추출되기 전에 힙화되어야 합니다. 나머지 요소의 힙은 다음과 같을 수 있습니다.

5를 추출하고 새 목록(배열)에 추가하면 결과가 제공됩니다.

그리고

나머지 세트를 heapify하면 다음이 제공됩니다.

6을 추출하고 새 목록(배열)에 추가하면 결과가 제공됩니다.

그리고

나머지 세트를 heapify하면 다음이 제공됩니다.

7을 추출하여 새 목록에 추가하면 다음과 같은 결과가 나타납니다.

그리고

나머지 세트를 heapify하면 다음이 제공됩니다.

9를 추출하고 새 목록에 추가하면 결과가 제공됩니다.

그리고

나머지 세트를 heapify하면 다음이 제공됩니다.

11을 추출하여 새 목록에 추가하면 다음과 같은 결과를 얻을 수 있습니다.

그리고

나머지 세트를 heapify하면 다음이 제공됩니다.

14개를 추출하여 새 목록에 추가하면 다음과 같은 결과를 얻을 수 있습니다.

그리고

나머지 세트를 heapify하면 다음이 제공됩니다.

15개를 추출하여 새 목록에 추가하면 다음과 같은 결과를 얻을 수 있습니다.

그리고

나머지 세트를 heapify하면 다음이 제공됩니다.

17을 추출하여 새 목록에 추가하면 다음과 같은 결과를 얻을 수 있습니다.

그리고

나머지 세트를 heapify하면 다음이 제공됩니다.

19를 추출하여 새 목록에 추가하면 다음과 같은 결과를 얻을 수 있습니다.

그리고

나머지 세트를 heapify하면 다음이 제공됩니다.

22개를 추출하여 새 목록에 추가하면 다음과 같은 결과를 얻을 수 있습니다.

그리고

나머지 세트를 heapify하면 다음이 제공됩니다.

24개를 추출하여 새 목록에 추가하면 다음과 같은 결과를 얻을 수 있습니다.

그리고

이제 힙 배열이 비어 있습니다. 처음에 있던 모든 요소는 이제 새 배열(목록)에 있고 정렬됩니다.

힙 정렬 알고리즘

독자가 교과서에서 힙 정렬이 두 단계로 구성되어 있음을 읽었을지라도 힙 정렬은 여전히 ​​주어진 배열을 반복적으로 축소하는 하나의 단계로 구성된 것으로 볼 수 있습니다. 이를 통해 heapsort로 정렬하는 알고리즘은 다음과 같습니다.

• 정렬되지 않은 목록을 쌓습니다.
• 힙의 첫 번째 요소를 추출하여 새 목록의 첫 번째 요소로 넣습니다.
• 나머지 목록을 쌓아 두십시오.
• 새 힙의 첫 번째 요소를 추출하고 새 목록의 다음 요소로 넣습니다.
• 힙 목록이 비어 있을 때까지 이전 단계를 순서대로 반복합니다. 마지막으로 새 목록이 정렬됩니다.

적절한 힙 정렬 시간 복잡도

1단계 접근 방식은 힙 정렬의 시간 복잡도를 결정하는 데 사용됩니다. 정렬할 정렬되지 않은 요소가 8개 있다고 가정합니다.

가능한 최대 작업 수는 다음과 같습니다.

이러한 작업 수의 평균은 다음과 같습니다.

이전 그림의 마지막 네 힙은 첫 번째 요소가 제거되었을 때 변경되지 않았습니다. 첫 번째 요소가 제거될 때 이전 힙 중 일부도 변경되지 않았습니다. 이를 통해 더 나은 평균 주요 작업(스와핑) 수는 4.5개가 아니라 3개입니다. 따라서 더 나은 총 평균 주요 작업 수는 다음과 같습니다.

로그 이후 _둘 8 = 3.

일반적으로 힙 정렬의 평균 케이스 시간 복잡도는 다음과 같습니다.

점이 곱셈을 의미하고 n이 N인 경우 목록(둘 중 하나)의 총 요소 수입니다.

첫 번째 요소를 추출하는 작업은 무시되었습니다. 시간 복잡도 주제에서 비교적 짧은 시간이 소요되는 작업은 무시됩니다.

C++로 코딩하기

C++의 알고리즘 라이브러리에는 make_heap() 함수가 있습니다. 구문은 다음과 같습니다.

벡터의 첫 번째 요소를 가리키는 반복자를 첫 번째 인수로 취한 다음 벡터의 끝 바로 너머를 가리키는 반복자를 마지막 인수로 취합니다. 이전의 정렬되지 않은 목록의 경우 구문은 다음과 같이 사용하여 최소 힙을 얻습니다.

이 코드는 벡터 콘텐츠를 최소 힙 구성으로 변경합니다. 다음 C++ 벡터에서는 두 개의 배열 대신 두 개의 벡터가 사용됩니다.

벡터의 첫 번째 요소를 복사하고 반환하려면 벡터 구문을 사용하십시오.

벡터의 첫 번째 요소를 제거하고 버리려면 벡터 구문을 사용하십시오.

벡터(다음 요소) 뒤에 요소를 추가하려면 벡터 구문을 사용하십시오.

프로그램의 시작은 다음과 같습니다.

알고리즘 및 벡터 라이브러리가 포함되어 있습니다. 프로그램의 다음은 heapsort() 함수입니다.

재귀함수입니다. C++ 알고리즘 라이브러리의 make_heap() 함수를 사용합니다. 함수 정의의 두 번째 코드 세그먼트는 힙 빌드 후 이전 벡터에서 첫 번째 요소를 추출하고 새 벡터의 다음 요소로 추가합니다. 함수 정의에서 벡터 매개변수는 참조이고 함수는 식별자(이름)로 호출됩니다.

이에 적합한 C++ 주 함수는 다음과 같습니다.

출력은 다음과 같습니다.

정렬(완전히).

결론

이 기사에서는 정렬 알고리즘으로서 일반적으로 힙 정렬로 알려진 힙 정렬의 특성과 기능에 대해 자세히 설명했습니다. Heapify Time Complexity, Heapsort 그림 및 알고리즘으로서의 Heapsort는 예제에서 다루고 지원합니다. 잘 작성된 힙 정렬 프로그램의 평균 시간 복잡도는 O(nlog(n))