Heap
Heap이란?
- Heap이란 데이터를 저장하는 자료구조 중 하나로, 힙트리(heap tree)라고도 부른다.
+특정한 조건을 만족하는 이진트리(binary tree)를 기반으로 구현된다.
Heap의 종류:
-
Max Heap: 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전이진트리이다.
-
Min Heap: 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전이진트리이다.
Heap의 활용 예시:
우선순위 큐(priority queue)
- Heap을 이용한 우선순위 큐 구현
데이터의 우선순위에 따라 값을 추가하고 제거할 수 있는 자료구조이다.
힙 정렬(heap sort)
- Heap을 이용한 정렬 알고리즘
최대값(Min Heap) 또는 최소값(Max Heap)을 추출하여 정렬된 순서대로 배열에 추가하는 과정을 반복한다.
최단 경로 알고리즘(shortest path algorithm)
- Heap을 이용하여 우선순위가 가장 높은 노드를 선택하고, 그 노드를 기준으로 다른 노드까지의 최단 경로를 계산하는 과정을 반복한다.
Heap의 구현 방법
-
배열을 이용한 구현: 완전이진트리를 배열에 저장하여 구현한다.
-
연결 리스트를 이용한 구현: 각 노드가 자식 노드를 가리키는 포인터를 가지는 구조이다.
Heap의 기본동작
삽입 (Insertion)
-
Heap에 새로운 값을 추가한다.
-
일반적으로는 트리의 맨 끝 노드에 새로운 값을 추가하고, 부모 노드와 비교하여 Heap 조건을 만족시키는 과정을 거친다.
삭제 (Deletion)
-
Heap에서 가장 큰 또는 가장 작은 값을 제거한다.
-
일반적으로는 Root 노드를 삭제하고, Heap 조건을 만족시키는 과정을 거친다.
Heap의 시간 복잡도
-
삽입의 시간 복잡도: O(log n)
-
삭제의 시간 복잡도: O(log n)
-
이진트리에서 깊이는 log n을 초과할 수 없으므로, Heap의 삽입과 삭제는 최악의 경우에도 O(log n)의 시간 복잡도를 가지낟.
Heap의 한계와 보완
-
Heap의 단점: Heap에서 원하는 값을 탐색하는 것은 비효율적이다.
-
Heap의 보완 방법:
이진 탐색(binary search)을 이용한 자료구조를 추가로 사용하여 보완
Heap 내에서 빠르게 탐색이 가능하도록 구현한다.
예제문제
알고리즘 수업 - 힙 정렬 2(백준 : 24174번)
오늘도 서준이는 최소 힙 기반 힙 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 힙 정렬로 배열 A를 오름차순 정렬할 경우 배열 A의 원소가 K 번 교환된 직후의 배열 A를 출력해 보자.
크기가 N인 배열에 대한 힙 정렬 의사 코드는 다음과 같다.
heap_sort(A[1..n]) { # A[1..n]을 정렬한다.
build_min_heap(A, n);
for i <- n downto 2 {
A[1] <-> A[i]; # 원소 교환
heapify(A, 1, i - 1);
}
}
build_min_heap(A[], n) {
for i <- ⌊n / 2⌋ downto 1
heapify(A, i, n)
}
# A[k]를 루트로 하는 트리를 최소 힙 성질을 만족하도록 수정한다.
# A[k]의 두 자식을 루트로 하는 서브 트리는 최소 힙 성질을 만족하고 있다.
# n은 배열 A의 전체 크기이며 최대 인덱스를 나타낸다.
heapify(A[], k, n) {
left <- 2k; right <- 2k + 1;
if (right ≤ n) then {
if (A[left] < A[right]) then smaller <- left;
else smaller <- right;
}
else if (left ≤ n) then smaller <- left;
else return;
# 최소 힙 성질을 만족하지 못하는 경우 재귀적으로 수정한다.
if (A[smaller] < A[k]) then {
A[k] <-> A[smaller];
heapify(A, smaller, n);
}
}입력
첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 교환 횟수 K(1 ≤ K ≤ 108)가 주어진다.
다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)
출력
배열 A에 K 번 교환이 발생한 직후의 배열 A를 한 줄에 출력한다. 교환 횟수가 K 보다 작으면 -1을 출력한다.
예제 입력 1
5 2
2 5 1 4 3
예제 출력 1
1 3 2 4 5
과정설명 :
2 5 1 4 3(heapify(A, 2, 5)) -> 2 3 1 4 5(heapify(A, 1, 5)) -> 1 3 2 4 5(A[1] <-> A[5]) -> 5 3 2 4 1(heapify(A, 1, 4)) -> 2 3 5 4 1(A[1] <-> A[4]) -> 4 3 5 2 1(heapify(A, 1, 3)) -> 3 4 5 2 1(A[1] <-> A[3]) -> 5 4 3 2 1(heapify(A, 1, 2)) -> 4 5 3 2 1(A[1] <-> A[2]) -> 5 4 3 2 1. 총 9회 교환이 발생하고 두 번째 교환 직후 배열 A의 모습은 1 3 2 4 5이다.
예제 입력 2
5 10
2 5 1 4 3
예제 출력 2
-1
과정설명 :
교환 횟수 9가 K 보다 작으므로 -1을 출력한다.
나의 생각
-
만약 k==0이면(교환 X) 자신을 출력시키고 바로 프로그램을 종료한다.
-
교환이 일어날때마다 count를 1증가시킨다.
-
재귀가 일어나기때문에 count를 전역변수로 고정하여 값을 보존하고, 공유한다.
-
k번째 교환이 일어나는 시점에 배열을 출력하고 프로그램을 종료하여 이후, 연산을 실행하지 않게 한다.
-
이를 위해 count가 어디서 증가하는지 코드를 읽고 파악해야만 한다.
구현
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
public class Main {
static int count = 0; // 비교 횟수를 카운트하기 위한 변수
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()); // 첫번째 줄 입력받기
int n = Integer.parseInt(st.nextToken()); // 배열의 크기
int k = Integer.parseInt(st.nextToken()); // 교환할 횟수
int[] a = new int[n]; // 배열 a
st = new StringTokenizer(br.readLine()); // 두번째 줄 입력받기
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(st.nextToken()); // 배열 a의 값들을 하나씩 넣어준다.
}
if (k == 0) { // k가 0인 경우 배열 a를 그대로 출력 (자신의 모습 그대로)
bw.write(String.join(" ", Arrays.stream(a)
.mapToObj(String::valueOf)
.toArray(String[]::new)) + "\n");
} else {
heapSort(a, n, k, bw); // 그 외의 경우 heapSort 메소드를 호출하여 k번 교환
}
bw.flush();
bw.close();
}
public static void heapify(int[] A, int k, int n, int k_value) { // 최소힙을 만들기 위한 heapify 메소드
int left = 2 * k; // 왼쪽 자식 노드의 인덱스
int right = 2 * k + 1; // 오른쪽 자식 노드의 인덱스
int smaller = k; // k의 인덱스
if (left <= n && A[left - 1] < A[smaller - 1]) { // 왼쪽 자식 노드가 존재하고 더 작은 경우
smaller = left; // smaller 변수를 왼쪽 자식 노드의 인덱스로 갱신
}
if (right <= n && A[right - 1] < A[smaller - 1]) { // 오른쪽 자식 노드가 존재하고 더 작은 경우
smaller = right; // smaller 변수를 오른쪽 자식 노드의 인덱스로 갱신
}
if (smaller != k) { // k의 값보다 자식 노드의 값이 더 작은 경우 교환
int temp = A[k - 1];
A[k - 1] = A[smaller - 1];
A[smaller - 1] = temp;
count += 1; // 비교 횟수 증가
if (count == k_value) { // 비교 횟수가 k와 같아지면 출력 후 코드 종료
String result = Arrays.stream(A)
.mapToObj(String::valueOf)
.collect(Collectors.joining(" "));
System.out.println(result); // k번째 교환된 배열 출력
System.exit(0);
}
heapify(A, smaller, n, k_value); // 자식 노드와 교환한 경우, 변경된 자식 노드를 기준으로 다시 heapify를 호출
}
}
public static void buildMinHeap(int[] A, int n, int k_value) { // 최소힙을 만들기 위한 buildMinHeap 메소드
for (int i = n / 2; i >= 1; i--) { // 마지막 단계의 부모 노드부터 heapify를 호출하여 최소힙 생성
heapify(A, i, n, k_value);
}
}
public static void heapSort(int[] A, int n, int k_value, BufferedWriter bw) throws IOException { // heapSort 메소드
buildMinHeap(A, n, k_value); // 최소힙 생성
for (int i = n; i >= 2; i--) { // 배열의 마지막 인덱스부터 시작하여 heapify를 호출하여 정렬 수행
int temp = A[0]; // 최소값과 맨 끝 값을 교환
A[0] = A[i - 1];
A[i - 1] = temp;
count += 1; // 비교 횟수 증가
if (count == k_value) { // 비교 횟수가 k와 같아지면 출력 후 코드 종료
String result = Arrays.stream(A)
.mapToObj(String::valueOf)
.collect(Collectors.joining(" "));
try {
bw.write(result + "\n"); // k번째 교환된 배열 출력
bw.flush();
bw.close();
System.exit(0);
} catch (Exception e) {// BufferedWriter 예외처리
e.printStackTrace();
}
}
heapify(A, 1, i - 1, k_value); // heapify를 호출하여 최소힙을 재구성
}
try {
bw.write("-1\n"); // 모든 교환이 이루어졌는데 여기까지 왔으면, -1 출력
bw.flush();
bw.close();
System.exit(0);
} catch (Exception e) { // BufferedWriter 예외처리
e.printStackTrace();
}
}
}
마무리
- 원래는 잘 안풀리면 다른 사람들의 샘플 코드를 보고 공부하며 풀었다.
- 그러나 자료를 찾지못하여, Heap정렬의 대해 공부하고, 혼자 고민하면서 문제를 해결했고 결국 성공했다. 그래서 시간이 오래 걸렸다...
자바로 문제를 맞춘사람이 아직 나 포함 2명밖에 없었다.
다른 사람들이 보다 적은 시행착오를 통해 Heap정렬에 대해 이해하고 문제풀이에 도전할 수 있기를 바라며, 코드를 공유한다.
