Understanding Heap Sort in Computer Algorithms (1/3)

Contents

1️⃣ 힙 정렬 (Heap sort)
2️⃣ 특수 정렬 (Special Alignment)
3️⃣ 셀 정렬 (Shell sort)
4️⃣ 정렬 알고리즘 간 성능 비교 (Performance comparison between sorting algorithms)

2,3,4 는 다음 편 참고 (I’m writing only Heap sort on this post, next topics will come along on next post)

힙 자료구조 #1 : 이진 트리의 개념

이진 트리(Binary Tree): 각 노드의 자식 노드의 개수가 2개 이하로 한정되는 트리

이진 트리의 종류 3가지에 대해 살펴보자. 이미지에서는 이진 트리의 다양한 유형을 보여주고 있다. 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조를 말한다. 이를 기반으로 여러 유형의 이진 트리가 존재한다.

1. 편향 이진 트리 (Skewed Binary Tree):

모든 노드가 한쪽으로만 치우친 트리이다.
이미지에서는 왼쪽으로 편향된 이진 트리를 보여주고 있다. 즉, 모든 노드가 왼쪽 자식만을 가지고 있다.
트리의 높이가 노드 수와 동일한 구조로, 트리의 성능이 비효율적일 수 있다.

2. 포화 이진 트리 (Full Binary Tree):

모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진 트리이다.
포화 이진 트리에서는 모든 노드가 완전히 자식 노드를 가진다.
즉, 각 레벨이 완전히 채워져 있는 트리로, 마지막 레벨을 제외한 모든 레벨에서 모든 노드가 두 개의 자식 노드를 가진다.

3. 완전 이진 트리 (Complete Binary Tree):

트리의 모든 레벨이 완전히 채워져 있고, 마지막 레벨만이 왼쪽에서 오른쪽으로 차례대로 노드가 채워지는 트리이다.
즉, 마지막 레벨을 제외한 나머지 레벨은 모두 자식 노드로 꽉 차 있으며, 마지막 레벨은 가능한 한 왼쪽에서부터 노드를 채워나간다.
힙(Heap) 구조에 자주 사용되는 트리이다.

이러한 이진 트리의 구조는 특정 문제나 요구 사항에 따라 사용됩니다.

힙 자료구조 #2 : 완전 이진 트리(Complete Binary Tree)

첫번째 트리(왼쪽 위): 마지막 레벨에 노드 4가 왼쪽부터 차례대로 채워졌고 마지막 레벨에서 오른쪽 자식 노드가 비어 있어도, 왼쪽부터 순서대로 채워졌기 때문에 완전 이진 트리이다.

두번째 트리 (오른쪽 위): 노드 4가 마지막 레벨의 오른쪽 자식으로 채워져 있어, 왼쪽 자식이 비어 있다. 완전 이진 트리에서는 마지막 레벨이 왼쪽부터 차례대로 채워져야 하므로 완전 이진 트리가 아니다.

세번째 트리 (왼쪽 아래): 마지막 레벨이 왼쪽부터 차례대로 채워져 있고 모든 레벨이 꽉 차 있기 때문에 완전 이진 트리이다.

네번째 트리 (오른쪽 아래): 마지막 레벨에서 6이 왼쪽에, 4가 왼쪽에 위치해 있다. 완전 이진 트리에서는 마지막 레벨이 왼쪽부터 순서대로 채워져야 하므로, 6 다음에 4가 오는 것이 아닌 4 다음에 6이 와야 한다. 따라서 완전 이진 트리가 아니다.

힙 자료구조 #3 : 힙(Heap)의 개념

💡요약: 힙은 특정 규칙을 만족하는 완전 이진 트리로, 최소 힙 또는 최대 힙으로 나눌 수 있으며, 각 노드의 값이 자식 노드의 값과 비교하여 크거나 작지 않은 관계를 유지한다. 힙 구조는 우선순위 큐, 힙 정렬 등 다양한 알고리즘과 데이터 처리에 유용하게 사용된다.

힙의 사전적 의미:
- 힙(Heap)은 아무렇게나 수북이 쌓아 올린 더미를 의미하며, 많은 양의 어떤 것들을 일컫는 단어이다.
- 단어 자체는 무질서하게 쌓여 있는 더미를 의미하지만, 자료구조에서의 힙은 특정한 규칙을 따르는 트리 구조를 의미한다.
힙 자료구조의 정의:
- 힙(Heap)은 각 노드가 값을 가지며, 자신의 자식 노드의 값과 특정한 관계를 유지하는 **완전 이진 트리(Complete Binary Tree)**이다.
- 힙 트리는 **최소 힙(Min Heap)**과 최대 힙(Max Heap) 두 가지로 나뉜다.

힙 자료구조 #4 힙의 종류

최소 힙: 부모 노드가 자식 노드보다 작거나 같은 값. 루트 노드는 트리에서 가장 작은 값.
최대 힙: 부모 노드가 자식 노드보다 크거나 같은 값. 루트 노드는 트리에서 가장 큰 값.
기본적으로 "힙"이라는 용어는 최대 힙을 의미한다.

1. 최소 힙(Min Heap)

부모 노드의 값이 자식 노드의 값보다 항상 작거나 같다는 조건을 만족하는 트리이다.
즉, 루트 노드는 항상 트리에서 가장 작은 값을 가진다.
이미지에서 왼쪽에 있는 트리는 최소 힙의 예시이다.
여기서 루트 노드 2는 가장 작은 값이며, 모든 부모 노드의 값이 자식 노드보다 작거나 같다

2. 최대 힙(Max Heap):

부모 노드의 값이 자식 노드의 값보다 항상 크거나 같다는 조건을 만족하는 트리이다.
즉, 루트 노드는 트리에서 가장 큰 값을 가진다.
이미지에서 오른쪽에 있는 트리는 최대 힙의 예시이다.

힙 자료구조 #5 힙이 아닌 트리의 예시

1. 왼쪽 트리: 완전 이진 트리 조건을 만족하지 않음

이 트리는 완전 이진 트리의 조건을 만족하지 않는다
완전 이진 트리의 조건은 모든 레벨이 왼쪽부터 순서대로 채워져야 하며, 마지막 레벨은 왼쪽부터 노드가 차례로 채워져야 하기 때문이다.
이 트리는 마지막 레벨에서 왼쪽에서 오른쪽으로 차례로 채워지지 않고, 오른쪽 자식 노드(4)가 비어 있는 상태가 되어, 완전 이진 트리의 구조를 위반하게 되었다.
결론: 이 트리는 완전 이진 트리가 아니므로 힙 구조로 사용할 수 없게된다.

2. 오른쪽 트리: 최대 힙 조건 위반

이 트리는 완전 이진 트리의 구조를 만족하지만, 최대 힙의 조건을 위반한다.
최대 힙은 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같아야 하기 때문이다.
이 트리에서는 오른쪽 자식 노드(1)와 그 자식 노드(8)의 관계에서 부모 노드(1)의 값이 자식 노드(8)의 값보다 작다
따라서 최대 힙 조건을 만족하지 않는다.

힙 자료구조 #6 배열을 이용한 힙의 표현

힙은 완전 이진 트리의 특성을 가지기 때문에, 배열을 사용하여 각 노드를 저장할 수 있으며, 배열의 인덱스를 통해 부모-자식 관계를 효율적으로 표현할 수 있다. 이 방법은 **힙 정렬(Heap Sort)**이나 **우선순위 큐(Priority Queue)**와 같은 알고리즘에서 매우 유용하게 사용된다.

1. 힙을 배열로 표현하는 방법

힙을 배열로 표현할 때 다음과 같은 규칙을 따른다:

배열의 0번째 인덱스는 루트 노드를 나타낸다.
배열의 각 레벨은 인덱스의 특정 범위로 나타난다:
- 레벨 0: 배열의 0번 인덱스 (루트 노드)
- 레벨 1: 배열의 1번과 2번 인덱스
- 레벨 2: 배열의 3번에서 6번 인덱스
- 레벨 3: 배열의 7번에서 14번 인덱스 (2ⁿ-1 ~ 2ⁿ⁺¹-2)
자식 노드의 인덱스는 부모 노드 인덱스를 기준으로 계산할 수 있다.
- 왼쪽 자식 노드의 인덱스: 2 * 부모 인덱스 + 1
- 오른쪽 자식 노드의 인덱스: 2 * 부모 인덱스 + 2
부모 노드의 인덱스는 자식 노드 인덱스를 기준으로 계산할 수 있다:
- 부모 노드의 인덱스: (자식 노드 인덱스 - 1) / 2

예를 들어, 인덱스 1에 있는 7의 자식 노드들은 다음과 같이 계산된다

- 왼쪽 자식: 2 * 1 + 1 = 3 (배열 A의 3번 인덱스 = 3)
- 오른쪽 자식: 2 * 1 + 2 = 4 (배열 A의 4번 인덱스 = 5)
- 인덱스 2에 있는 6의 자식 노드들은 다음과 같이 계산된다: 왼쪽 자식: 2 * 2 + 1 = 5 (배열 A의 5번 인덱스 = 4) - 오른쪽 자식: 2 * 2 + 2 = 6 (배열 A의 6번 인덱스 = 1

힙의 구성과 삭제 #1 : 힙의 구성

힙 정렬을 수행하기 위해서는 완전 이진 트리(**Complete Binary Tree)**의 특성을 유지하면서 부모 노드와 자식 노드 간의 힙조건(최대 힙 또는 최소 힙)을 만족하도록 각 노드와 값을 재배치하는 것이다. 말단 노드를 제외한 가장 하위 레벨의 부모 노드로부터 우측에서 좌측으로 이동하면서 힙을 구성하고 마지막으로 루트 노드에서 종료된다.

1. 힙의 구성 개요

힙 정렬을 수행하기 위해서는 먼저 힙을 구성해야 한다.
힙을 구성할 때, 완전 이진 트리의 형태를 유지하면서, 최대 힙(Max Heap) 또는 **최소 힙(Min Heap)**의 조건을 만족하도록 각 노드의 값을 재배치한다.
힙의 조건:
- 최대 힙: 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같아야 한다.
- 최소 힙: 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같아야 한다.

2. 힙의 구성 절차

힙을 구성할 때는 말단 노드를 제외한 부모 노드부터 시작하여, 가장 하위 레벨에서 루트 노드 방향으로 이동하며 힙 조건을 만족하도록 재배치한다.
힙 구성의 순서:
1. 말단 노드를 제외한 가장 하위 레벨의 부모 노드부터 시작하여 재배치를 수행한다.
2. 우측에서 좌측으로 순서를 따라가며 각 노드를 힙 조건에 맞추어 재배치한다.
3. 각 부모 노드의 자식 노드들이 힙 조건을 만족할 때까지 자식과 부모의 값을 비교하고, 필요에 따라 값을 교환한다.

3. 이미지 설명

이미지에서는 주어진 트리를 힙의 규칙에 맞게 재배치하는 과정을 보여주고 있다. 힙의 구성 순서는 다음과 같다:

Step 1: 가장 하위 레벨의 **좌측 노드(7)**부터 시작하여 힙 조건을 만족하도록 재배치한다.
Step 2: 그 다음 **우측의 부모 노드(9)**를 확인하고 힙 조건을 만족하도록 재배치한다.
Step 3: 마지막으로 **루트 노드(6)**까지 이동하며 전체 트리를 힙 구조로 재배치한다.

4. 힙의 재배치 방법 (우측에서 좌측으로 수행)

우측에서 좌측으로 수행한다는 의미는, 말단 레벨의 가장 우측 부모 노드부터 순서대로 좌측 부모 노드로 이동하면서, 자식 노드와 비교하여 재배치를 수행한다는 것을 의미한다.
예를 들어, 위 이미지에서는 레벨 2의 우측에 위치한 3 노드부터 시작하여 9 노드, 6 노드 순서로 힙 조건을 만족시키며 트리를 재배치하고 있다.

5. 결론

힙을 구성하는 절차는 완전 이진 트리의 특성을 유지하면서, 부모 노드와 자식 노드 간의 힙 조건(최대 힙 또는 최소 힙)을 만족하도록 각 노드의 값을 재배치하는 것입니다.
말단 노드를 제외한 가장 하위 레벨의 부모 노드부터 우측에서 좌측으로 이동하면서 힙을 구성하고, 마지막으로 루트 노드에서 종료됩니다.

힙의 구성과 삭제 #2 : 스며 내리기(Percolate Down)

**스며 내리기(Percolate Down)**는 힙을 구성하거나 재배치할 때 주로 사용되는 연산 중 하나로, 루트 노드를 기준으로 하여 힙의 조건을 만족할 때까지 노드를 아래로 내려가며(스며 내려가며) 재배치하는 방법이다. 이 과정은 힙의 규칙을 위반한 서브 트리의 루트 노드를 올바른 위치로 재배치하여 힙의 조건을 만족시키기 위한 중요한 단계라고 할 수 있다.

1. 스며 내리기(Percolate Down)의 개념

스며 내리기는 루트 노드를 기준으로 아래로 이동하며 힙의 규칙에 맞게 재배치하는 과정이다.
물이 화분에서 아래로 스며드는 것처럼, 주어진 노드를 자식 노드들과 비교하여 적절한 위치로 스며 내리게 만든다.
스며 내리기는 주로 힙 삭제 또는 힙 구성 시 루트 노드를 재배치할 때 사용된다.

2. 스며 내리기 과정 설명 (최대 힙을 기준으로 설명)

스며 내리기는 부모 노드의 값이 자식 노드의 값보다 크거나 같은지 비교하여, 만약 조건을 만족하지 않으면 자식 노드 중 더 큰 값과 교환하면서 재배치하게 된다.
아래는 스며 내리기 과정의 주요 단계입니다:
1. 루트 노드를 선택하여 자식 노드들과 비교한다.
2. 두 자식 노드 중 더 큰 값을 가진 자식 노드를 선택한다.
3. 부모 노드의 값이 선택된 자식 노드의 값보다 작다면, 부모 노드와 자식 노드의 값을 교환한다.
4. 교환된 자식 노드 위치에서 다시 자식 노드들과 비교하여 스며 내리기를 반복한다.
5. 더 이상 교환이 필요 없을 때까지, 또는 자식 노드가 없을 때까지 스며 내리기를 수행하게 된다.

힙의 구성과 삭제 #3 : 힙의 구성 예시 1

초기상태: 트리의 형태는 배열의 순서대로 노드를 배치한 상태이다.
첫 번째 재배치(1단계, 교환됨): 말단 레벨의 왼쪽 부모 노드(7)에서 스며 내리기를 시작하여 7과 자식 노드 1, 9 중 가장 큰 값 9와 교환하였다.
두 번째 재배치(2단계, 교환됨): 다음 부모 노드(2)에서 스며 내리기를 수행한다. 2와 자식 노드 3, 9 중 가장 큰 값 9와 교환한다.

힙의 구성과 삭제 #4 : 힙의 구성 예시 2

위에서 언급된 방식과 동일하게 교환이 진행되고 각 단계에서 부모 노드의 값이 자식 노드의 값보다 크거나 같은지를 확인하고, 조건을 만족하지 않으면 더 큰 값을 가진 자식 노드와 교환한다. 이 과정을 스며 내리기 (Percolate Down) 연산이라고 한다. 교환이 완료된 후, 최종적으로 최대 힙의 조건(부모 노드가 자식 노드보다 항상 크거나 같음)을 만족하는 트리를 구성하게 된다.

힙의 구성과 삭제 #5 : 힙 구성의 의사코드

힙 구성 알고리즘은 주어진 배열을 힙의 조건에 맞도록 재배치하여 최대 힙 또는 최소 힙을 구성하는 방법을 설명한다. 알고리즘은 스며 내리기(Percolate Down) 연산을 통해 각 노드를 재배치하여 힙을 구성하게 된다.

알고리즘 설명

입력:
- 배열 A[0...n-1]: 힙을 만들고자 하는 배열이다. 이 배열의 원소들을 힙 구조로 재배치하여 힙을 구성한다.
변수 설명:
- i: 스며 내리기를 수행할 노드의 인덱스이다.
- i의 초기값은 배열의 말단 노드(n-1)의 부모 노드 인덱스 (n-2)/2에서 시작한다.
- i는 (n-2)/2부터 0까지 감소하며, 배열의 오른쪽에서 왼쪽으로 이동하면서 각 노드에서 스며 내리기를 수행하게 된다.
알고리즘의 단계:
1. for 문:
  - for i ← (n-2)/2 downto 0:
    - 배열의 오른쪽 말단 노드의 부모 노드 (n-2)/2 인덱스부터 시작하여 0까지 왼쪽으로 이동하면서 각 노드에서 스며 내리기(Percolate Down) 연산을 수행한다.
2. 스며 내리기 연산:
  - percolateDown(A, i);
    - i 인덱스의 노드를 루트로 하는 서브 트리에서 스며 내리기를 수행하여, 해당 서브 트리가 힙의 조건을 만족하도록 재배치한다.
출력:
- 주어진 배열 A가 힙 조건을 만족하도록 재배치된다.

힙의 구성과 삭제 #6 : 스며 내리기의 의사코드

스며내리기 알고리즘은 주어진 노드를 기준으로 해당 노드와 자식 노드들을 비교하여 힙의 조건을 만족하도록 재배치하는 과정이다. 주로 힙 구성 또는 힙 정렬 시에 사용된다.

입력:
- A[]: 배열 (힙의 원소들이 저장된 배열)
- k: 스며 내리기를 수행할 노드의 인덱스
출력: 없음 (배열 A[]가 수정됨)

알고리즘의 동작 원리

child와 right 자식 노드 인덱스 계산:
- child = 2k + 1 : k 노드의 왼쪽 자식 노드 인덱스
- right = 2k + 2 : k 노드의 오른쪽 자식 노드 인덱스
왼쪽 자식 노드 존재 여부 확인:
- if (child <= n-1) :
  - child가 배열 A의 인덱스 범위(n-1) 이내에 있는지 확인한다.
  - 만약 child가 범위를 벗어난다면, k는 말단 노드이므로 더 이상 스며 내리기 연산을 수행하지 않는다.
오른쪽 자식 노드 존재 여부 및 값 비교:
- if (right <= n-1 and A[child] < A[right]) :
  - right가 배열 A의 인덱스 범위(n-1) 이내에 있는지 확인한다.
  - 만약 right가 범위 내에 있고, A[child] < A[right]인 경우, child를 오른쪽 자식 노드로 설정한다.
부모 노드와 자식 노드의 값 비교:
- if (A[k] < A[child]) :
  - k 노드의 값(A[k])이 child 노드의 값(A[child])보다 작으면 두 값을 교환한다.
재귀 호출:
- percolateDown(A, child) :
  - 교환이 발생한 경우, 새로운 child를 기준으로 다시 percolateDown을 호출하여 서브 트리에서도 힙 조건을 만족하도록 재배치한다.

힙의 구성과 삭제 #7 : 힙의 삭제

힙 정렬 과정에서 루트 노드 제거 후 재배치

**힙 정렬(Heap Sort)**을 수행할 때 루트 노드를 제거하고 재배치하는 과정을 살펴보자. 힙 정렬의 주요 단계는 다음과 같다.

루트 노드 제거:
- 힙의 최대값 또는 최소값은 항상 루트 노드에 위치한다.
- 따라서 힙 정렬을 수행할 때는 루트 노드를 제거하고, 그 자리에 **맨 끝 원소(말단 노드)**를 이동시킨다.
- 예를 들어, 아래의 그림에서 힙의 루트 노드 9를 제거하고, 맨 끝 원소 3을 루트 노드 자리로 이동시킨다.
스며 내리기(Percolate Down) 수행:
- 새로운 루트 노드를 기준으로, 스며 내리기 연산을 수행하여 힙의 조건을 다시 만족시키도록 한다.
- 루트 노드와 자식 노드들 간의 비교를 통해, 루트 노드의 값이 자식 노드들의 값보다 항상 크거나(최대 힙) 작도록(최소 힙) 재배치한다.
- 그림에서는 새로운 루트 노드 3이 왼쪽 자식 노드 8보다 작으므로, 스며 내리기 연산을 수행하여 3을 하위 노드로 내려보낸다.

루트 노드 제거: 루트 노드 9를 제거하고, 그 자리에 맨 끝 원소인 A[n-1] 맨 끝 노드 3을 루트 자리에 놓는다. 그리고 새로운 루트 노드를 시작으로 스며 내리기를 한 번 수행한다.

힙의 구성과 삭제 #8 : 힙의 삭제 2

스며 내리기 수행: 새로운 루트 노드 3을 스며 내리기 연산으로 재배치한다. 3과 자식 노드 8을 비교하고, 3을 자식 노드 8과 교환한다.

최종 힙 구조: 계속해서 스며 내리기를 수행하여 힙의 성질을 만족시킨다. 최종적으로 루트 노드 3이 자식 노드 4보다 작지 않도록 다시 재배치되어 힙의 성질을 만족하게 된다. 이와 같은 방식으로 힙 정렬은 최악의 경우에도 O(n log n)의 시간 복잡도를 가진다.

힙의 구성과 삭제 #9 : 힙 삭제의 의사코드

위의 이미지는 힙에서 루트 노드를 제거하는 과정을 설명하는 의사코드를 보여주고 있다. **힙 삭제(Heap Deletion)**는 주로 최대 힙 또는 최소 힙에서 루트 노드를 제거하고, 그 자리에 맨 끝 노드를 이동시킨 후, 스며 내리기 연산을 통해 힙의 조건을 유지하는 과정이다. 배열의 크기를 줄여가며 루트 노드를 제거하므로, 힙 정렬을 수행할 때 유용하게 사용할 수 있다. 이 알고리즘을 반복적으로 수행하면, 주어진 배열을 정렬할 수 있다. (힙 정렬의 기본 원리)

알고리즘 단계별 설명

현재 루트 노드 값 저장:
- max ← A[0]
- 현재 힙의 루트 노드 값(최대값 또는 최소값)을 max 변수에 저장한다.
맨 끝 자식 노드를 루트 노드로 지정:
- A[0] ← A[n-1]
- 배열의 맨 마지막 원소를 루트 노드 자리(A[0])에 넣는다.
배열 원소 수 감소:
- n = n - 1
- 힙에서 루트 노드가 제거되었으므로, 배열의 크기(원소 수)를 하나 줄인다.
루트 노드를 기준으로 스며 내리기(Percolate Down) 수행:
- percolateDown(A, 0)
- 새로운 루트 노드를 기준으로 힙의 성질을 만족하도록 스며 내리기 연산을 수행한다.
- 부모 노드와 자식 노드들을 비교하면서, 힙의 조건을 유지하도록 부모-자식 간 교환을 반복한다.
기존 루트 값 반환:
- return max
- 제거된 기존 루트 노드의 값을 반환한다.

힙 정렬의 의사코드와 분석 #1 : 힙 정렬의 개요

힙 정렬 (Heap Sort)
- 힙 정렬은 주어진 배열을 먼저 힙 구조로 만든 다음, 루트 노드(최대 또는 최소 요소)를 반복적으로 제거하여 배열을 정렬하는 알고리즘이다.
- 힙 구조란 완전 이진트리의 형태로 배열된 숫자들을 의미한다.
알고리즘 단계:
- 첫 번째 패널 (주어진 배열)
  - 주어진 배열 [4, 2, 8, 7, 3, 3, 5, 1, 9]의 이진 트리 표현을 보여준다.
  - 배열의 요소들이 이진 트리 형태로 구성되어 있다.
  - 힙 구조화 이전의 초기 상태를 나타낸다.
- 두 번째 패널 (힙 구성)
  - 주어진 배열을 힙 구조로 변환한 상태를 보여준다.
  - 트리가 최대 힙 또는 최소 힙의 속성을 만족하도록 재배열되었다. 부모 노드가 자식 노드보다 크거나(또는 작거나) 같은 힙 구조이다.
- 세 번째 패널 (힙 삭제):
  - 루트에 있는 가장 큰(또는 가장 작은) 요소가 제거된다.
  - 요소가 제거된 후, 힙 속성을 유지하도록 힙을 조정한다.
  - 이러한 과정을 전체 배열이 정렬될 때까지 반복하게 된다.

힙 정렬의 의사코드와 분석 #2 : 힙 정렬의 의사코드

위의 의사코드는 **힙 정렬(Heap sort)**의 기본 동작을 단계별로 보여주며, 힙을 먼저 구성한 후, 루트 노드를 반복적으로 제거하여 정렬된 배열을 만드는 과정을 설명하고 있다. deleteMax() 함수는 힙의 루트(최대값 또는 최소값)를 제거하는 작업을 수행한다.

의사코드 설명:

buildHeap():
- 주어진 배열을 힙 구조로 변환한다. 이는 힙의 속성을 만족하는 최대 힙 또는 최소 힙으로 구성하는 단계이다.
for i ← n-1 downto 1:
- 배열의 마지막 인덱스 n-1부터 1까지 반복한다. downto는 역순으로 순회를 의미한다.
A[i] ← deleteMax(A):
- 힙에서 루트 노드를 하나씩 제거하여 A 배열의 뒷자리부터 채워나간다. 루트 노드는 최대값이기 때문에 제거 후, 배열의 뒤에서부터 채우는 방식으로 정렬을 진행한다.

오른쪽 텍스트 설명:

1 : 힙을 구성
- buildHeap()을 통해 주어진 배열을 힙으로 변환한다.
2 : for 루프를 n-1 번 반복
- 배열의 마지막 인덱스에서 1까지 루프를 n-1번 반복한다.
3 : 힙에서 루트 노드를 하나씩 제거하여 A 배열의 맨 뒷자리부터 채워 나감
- deleteMax(A)를 통해 힙의 루트 노드를 제거하고, 제거된 값을 배열의 뒷자리부터 채워 넣는다.

힙 정렬의 의사코드와 분석 #1 : 힙 정렬의 시간 복잡도

시간 복잡도 분석:

buildHeap():
- buildHeap()은 percolateDown() 함수를 약 n/2번 호출한다.
- percolateDown() 함수는 주어진 노드를 아래로 내려가며 힙 구조를 만드는 작업을 수행한다.
- percolateDown() 함수의 수행 시간은 최대 O(log n)이지만, 전체 buildHeap()의 시간 복잡도는 Θ(n)이다.
  - 이유: n/2번 호출되지만 각 호출에서 이동하는 높이가 점점 줄어들기 때문이다.
for 루프:
- for 루프는 n-1번 반복됩니다. 즉, 배열의 모든 요소에 대해 deleteMax()를 호출하며 힙 정렬을 수행한다.
deleteMax():
- deleteMax() 함수는 힙에서 루트 노드를 제거하고, 힙 구조를 재정렬하는 함수이다.
- 최악의 경우 힙의 높이만큼 이동이 발생하므로, deleteMax()의 수행 시간은 Θ(log n)이다.
힙 정렬 전체의 시간 복잡도:
- 힙 정렬의 전체 시간 복잡도는 buildHeap()의 Θ(n) 시간과 n-1번 반복되는 deleteMax()의 Θ(log n) 시간을 고려하여 Θ(n log n)이다.

💡요약:

buildHeap()의 시간 복잡도: Θ(n)
deleteMax()의 시간 복잡도: Θ(log n)
힙 정렬 전체의 시간 복잡도: Θ(n log n)

요약

Command Palette