Implementation (Part 1)

Coddy의 힙 정렬 - DSA 시리즈 코스 레슨 — 9개 중 5번째.

우리는 힙 정렬(Heap Sort)을 핵심 연산부터 차근차근 구현해 보겠습니다.

챌린지

쉬움

힙 정렬(Heap Sort)의 핵심은 sift-down 연산입니다. 이것을 먼저 구현해 봅시다.

배열 arr(이진 힙으로 간주됨)와 인덱스 i를 매개변수로 받는 siftDown이라는 함수를 작성하세요. 이 함수는 해당 노드를 아래로 밀어내어 최대 힙(max-heap) 속성을 복원해야 합니다. 노드를 2*i + 1과 2*i + 2에 위치한 두 자식 노드와 비교하여, 더 큰 자식 노드가 부모보다 크면 서로 교체하고 해당 자식의 위치에서 과정을 반복합니다. 마지막으로 배열을 반환합니다.

예를 들어, siftDown([1, 10, 5, 3, 2], 0)은 [10, 3, 5, 1, 2]를 반환합니다.

직접 해보기

#include <stdlib.h>

int* siftDown(int* arr, int arr_size, int i, int* returnSize) {
    // 여기에 코드를 작성하세요
    *returnSize = arr_size;
    return arr;
}

실력 점검

이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.

힙 정렬 - DSA 시리즈의 모든 레슨

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2