6069 : 힙 정렬 구현
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
힙 정렬 구현
주어진 리스트를 힙 구조로 만든 후 최솟값/최댓값을 하나씩 추출하여 정렬하는
힙 정렬(Heap Sort) $O(N \log N)$을 직접 구현하시오.
조건: Python의
힌트:
1. 배열을 최대힙으로 만듭니다 (Build-Max-Heap).
2. 루트(최댓값)와 마지막 원소를 교환하고 힙 크기를 줄입니다.
3. 교환된 루트에 Heapify-Down을 수행합니다.
4. 반복하면 오름차순 정렬이 완성됩니다.
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
주어진 리스트를 힙 구조로 만든 후 최솟값/최댓값을 하나씩 추출하여 정렬하는
힙 정렬(Heap Sort) $O(N \log N)$을 직접 구현하시오.
조건: Python의
heapq를 사용하지 않고 직접 구현해야 합니다.힌트:
1. 배열을 최대힙으로 만듭니다 (Build-Max-Heap).
2. 루트(최댓값)와 마지막 원소를 교환하고 힙 크기를 줄입니다.
3. 교환된 루트에 Heapify-Down을 수행합니다.
4. 반복하면 오름차순 정렬이 완성됩니다.
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
입력 설명
첫째 줄에 정수의 개수 N (1 ≤ N ≤ 50,000)이 주어집니다.
둘째 줄에는 N개의 정수가 공백으로 구분되어 주어집니다.
둘째 줄에는 N개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
정렬된 N개의 정수를 공백으로 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
3 1 4 1 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 1 3 4 5