# Understanding Heap Sort in Computer Algorithms (1/3)

**Contents**

---

**<mark>1️⃣</mark>** <mark> 힙 정렬 (Heap sort)<br></mark>**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개 이하로 한정되는 트리

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727601519421/0358282f-78df-4579-9130-f3d8a08a9c78.png align="center")

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

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

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

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

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

### <mark>3. </mark> **<mark>완전 이진 트리 (Complete Binary Tree)</mark>**<mark>:</mark>

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

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727602040150/d52a328d-6499-485d-9d0c-5f95c70aca50.png align="center")

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

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

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

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727602638381/bf47c5d9-ac1f-4948-ad61-2b4fbf7bfc1e.png align="center")

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

---

### **힙 자료구조 #4 힙의 종류**

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727602691304/5960ac7e-e68c-4ce4-a2bb-7293297f3c74.png align="center")

### 1\. **최소 힙(Min Heap)**

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

### 2\. **최대 힙(Max Heap)**:

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727602943885/0368a230-a60f-4903-b552-e3ffb2a23dfe.png align="center")

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

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

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

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727605279008/9129d63c-46bb-4f17-92c7-5b1e4ba36672.png align="center")

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

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

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727607204190/c66737bf-9ad0-4cab-acee-33e0aadaa3bb.png align="center")

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

### 1\. 힙의 구성 개요

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

### 2\. 힙의 구성 절차

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

### 3\. 이미지 설명

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

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

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

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

### 5\. 결론

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727758199628/95221dd7-ee31-414b-8c5f-647e8c36c810.png align="center")

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

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

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

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

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727760826682/fff07b85-066c-48db-ac4a-7c2e251571a7.png align="center")

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727760840007/4a9f8c9c-ea0e-4547-bb3a-1f5abf66b4bd.png align="center")

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727761570842/04d711ac-2f6d-421d-83f7-ced404e9b001.png align="center")

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

#### 알고리즘 설명

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727762840921/dc425d45-ade3-41f6-8c97-b65829b76b75.png align="center")

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

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

### 알고리즘의 동작 원리

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

---

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

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

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727763401210/50ee8613-b20e-480e-be60-a2a4a867cb5b.png align="center")

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727763645525/3ca44178-1f41-48b6-826a-b4ba3ff1c651.png align="center")

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

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727763786071/32826009-910a-481b-a1ba-dfb0305079b7.png align="center")

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

#### 알고리즘 단계별 설명

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727774908327/ef43c787-0a69-432a-a16e-aff8d474c0bc.png align="center")

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727775277690/9f469237-3c96-47ec-aa8a-2a85411f3715.png align="center")

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

### 의사코드 설명:

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

### 오른쪽 텍스트 설명:

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

---

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

### 시간 복잡도 분석:

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

### <mark>💡요약:</mark>

* `buildHeap()`<mark>의 시간 복잡도: </mark> `Θ(n)`
    
* `deleteMax()`<mark>의 시간 복잡도: </mark> `Θ(log n)`
    
* **<mark>힙 정렬 전체의 시간 복잡도</mark>**<mark>: </mark> `Θ(n log n)`
    

---

요약

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727847244175/e4ffab87-0da0-4735-8fc5-7c803ad674f3.png align="center")