[자료구조 Heap / Java]
cs 스터디의 첫 주 과제인 Heap!
다음 영상을 보고 공부했다 👍🏻
https://www.youtube.com/watch?v=i9v-Q65d7wE&list=PLlTylS8uB2fCoXCVtfJ0wzotOU8a3ti6M&index=5
힙(Heap)은 이진 트리의 응용 버전이다.
- 완전 이진트리 형태의 자료구조
- 일차원 배열로 구현
- 데이터의 삽입과 삭제 시간이 빠르다: O(log N)
- 일반적으로 그룹을 정렬하거나 입력된 데이터 안에서 최소/최대 값을 찾을 때 사용한다.
- 중복을 허용한다.
힙의 종류는 두 가지, 최대 힙과 최소 힙으로 나뉜다.
- 최대 힙(Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큼
- 최소 힙(Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작음
- 부모 노드의 키 값이 자식 노드의 키 값보다 작은/큰 관계가 유지되므로, 트리 내에서 가장 작은/큰 키 값을 가진 노드는 항상 루트 노드가 됨.
힙은 어떻게 구현할까?
삽입 연산과 삭제 연산이 있다.
삽입 연산
1. 트리의 가장 마지막 위치에 노드를 삽입한다.
2. 추가된 노드와 그 부모 노드가 힙 조건(최대/최소)을 만족하는지 확인한다.
3. 만족하지 않는다면 부모와 자식의 키 값을 바꾼다.
4. 조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2~3을 반복한다.
==> 이 때, 노드의 개수가 N이라면 수행시간은 O(logN)이다.
삭제 연산
1. 힙의 삭제연산은 항상 루트 노드를 삭제한다.
2. 트리의 가장 마지막 노드를 루트 자리로 삽입한다.
3. 바꾼 위치의 노드가 힙 조건(최대/최소)을 만족하는지 확인한다.
4. 만족하지 않는다면 왼쪽 자식과 오른쪽 자식 중 적합한 노드와 키 값을 바꿈
5. 조건을 만족하거나 리프 노드에 도달할 때까지 3~4를 반복
==> 이 때, 노드의 개수가 N이라면 수행시간은 O(logN)이다.
package studio.aroundhub.codeground.lecture.heap;
import java.util.ArrayList;
import java.util.Scanner;
/**
* Maximum Heap Code
* thinkground.studio
* YouTube : Around Hub Studio
* @author Flature
*/
public class MaxHeap {
public static class MaximumHeap {
private ArrayList<Integer> heap;
public MaximumHeap() {
heap = new ArrayList<>();
heap.add(1000000); // heap.add(Integer.MAX_VALUE);
}
public void print() {
for (int i = 1; i < heap.size(); i++) {
System.out.print(heap.get(i) + " ");
}
System.out.println();
}
public void insert(int val) {
heap.add(val);
int p = heap.size() - 1;
while (p > 1 && heap.get(p / 2) < heap.get(p)) { // p/2는 부모 노드의 위치를 나타낸다.
System.out.println("swap");
int temp = heap.get(p / 2);
heap.set(p / 2, heap.get(p));
heap.set(p, temp);
p = p / 2;
}
}
public int delete() {
if (heap.size() - 1 < 1) { //삭제할 것이 없다!
return 0;
}
int deletedItem = heap.get(1);
heap.set(1, heap.get(heap.size() - 1)); // 루트 노드의 위치에 마지막 노드의 값을 넣어준다.
heap.remove(heap.size() - 1);
int pos = 1; //위치를 루트노드로 설정
while ((pos * 2) < heap.size()) { //pos * 2는 왼쪽에 있는 자식 노드 , 있는지 확인
int max = heap.get(pos * 2);
int maxPos = pos * 2;
if (((pos * 2 + 1) < heap.size()) && max < heap.get(pos * 2 + 1)) { // pos * 2 + 1 은 오른쪽 자식 노드
max = heap.get(pos * 2 + 1);
maxPos = pos * 2 + 1;
}
if (heap.get(pos) > max) {
break;
}
int temp = heap.get(pos);
heap.set(pos, heap.get(maxPos));
heap.set(maxPos, temp);
pos = maxPos;
}
return deletedItem;
}
}
// 15 9 5 7 4 3
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 내가 작업하고 싶은 횟수
MaximumHeap maximumHeap = new MaximumHeap();
for (int i = 0; i < N; i++) {
int val = sc.nextInt();
if (val == 0) {
System.out.println(maximumHeap.delete());
} else if (val == -1) {
maximumHeap.print();
} else {
maximumHeap.insert(val);
}
}
}
}
힙은 왜 사용할까?
최솟값이나 최댓값을 찾기 위해 배열을 사용한다면 O(N)의 시간복잡도가 소요된다.
그러나 힙을 사용하면 O(logN)만큼 소요되므로 훨씬 빠른 속도의 효율을 낼 수 있다.
이러한 힙 자료구조는 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아내야 하는 알고리즘 등에 활용된다.