Heap : 최대 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진 트리 기반 자료구조.
max heap : 부모노드는 자식노드보다 크다.
min heap : 부모노드는 자식노드보다 작다.
최대 힙 구현하기
1.MaxHeap
public class MaxHeap {
public int[] elements;
public int size;
public int capacity;
public MaxHeap CreateHeap(int capacity) { // 새로운 capacity의 힙 생성
MaxHeap mh = new MaxHeap();
mh.capacity = capacity;
mh.size = 0;
mh.elements = new int[mh.capacity + 1];
return mh;
}
public void MakeHeap(MaxHeap mh, int index) {
if (index / 2 > 0) { // 부모가 0보다 크다 = 부모가 있을 경우
if (mh.elements[index / 2] < mh.elements[index]) { // 만약 부모가 자식보다 작은 값일 경우에 스왑
swap(mh, index / 2, index);
}
MakeHeap(mh, index / 2); // 바뀐 혹은 그대로인 부모 값에 대하여 재귀. 그대로인 부모 값일 경우 바로 다음 재귀에서 중단됨 (이미 정렬된 힙)
}
}
public void swap(MaxHeap mh, int i, int j) {
int temp = mh.elements[i];
mh.elements[i] = mh.elements[j];
mh.elements[j] = temp;
}
public void Insert(MaxHeap mh, int element) {
if (mh.size == mh.capacity) { // heap 이 꽉 찬 상태
System.out.println("Insert : Max Heap is full");
} else if (mh.size == 0) { // heap 이 비어있는 상태
mh.size++;
mh.elements[mh.size] = element;
} else { // heap에 원소가 있으므로 일단 맨 뒤에 추가하고
mh.size++;
mh.elements[mh.size] = element;
MakeHeap(mh, mh.size); // 추가 후 해당 값에 대해 MakeHeap 진행
}
}
public void DeleteMax(MaxHeap mh) {
if (mh.size == 0) // 비어있는 heap
System.out.println("Delete : Max Heap is empty");
else { // 일단 맨 앞의 element를 맨 뒤의 element와 같은 값으로 설정
mh.elements[1] = mh.elements[mh.size];
mh.size--; // 그 후 size를 줄여주면 자연스레 마지막 값은 사라짐
for (int i = 1; i <= mh.size; i++)
MakeHeap(mh, i); // 루트 값부터 모든 값에 대하여 정렬 시작. 위에서부터 트리를 정렬.
}
}
public void PrintHeap(MaxHeap mh) {
if (mh.size == 0) {
System.out.println("Print : Max Heap is empty");
} else {
for (int i = 1; i <= mh.size; i++) {
System.out.print(mh.elements[i] + " ");
}
System.out.println();
}
}
}
2. Main
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
MaxHeap mh = new MaxHeap();
BufferedReader br = new BufferedReader(new FileReader("input.txt"));
String line = "";
while ((line = br.readLine()) != null) {
String[] lines = line.split(" ");
if (lines[0].equals("n")) {
mh = mh.CreateHeap(Integer.parseInt(lines[1]));
} else if (lines[0].equals("i")) {
mh.Insert(mh, Integer.parseInt(lines[1]));
} else if (lines[0].equals("d")) {
mh.DeleteMax(mh);
} else if (lines[0].equals("p")) {
mh.PrintHeap(mh);
}
}
br.close();
}
}
재귀의 힘. 코드가 간결하다.
'Code IT > Data-Structure' 카테고리의 다른 글
[자료구조] Hashing 해싱 (0) | 2021.04.03 |
---|---|
[자료구조] Binary Tree 이진 트리, Binary Search Tree 이진 탐색 트리 (0) | 2021.04.03 |
[자료구조] Circular Queue 원형 큐 (0) | 2021.04.03 |
[자료구조] 중위표기식, 후위표기식, 변환 (0) | 2021.04.03 |
[자료구조] LinkedList 연결 리스트 (0) | 2021.04.03 |
댓글