⚡ Tree (2)
📌 수식 트리
🔷 수식을 표현하는 이진 트리
- 수식 이진트리라고 부르기도 한다.
- 연산자는 루트 노드이거나 가지 노드
- 피연산자는 모두 리프 노드
📌 힙(Heap)
🔷 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
최대 힙(max heap)
- 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 >= 자식 노드의 키 값
- 루트 노드: 키 값이 가장 큰 노드
최소 힙(min heap)
- 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 <= 자식 노드의 키 값
- 루트 노드: 키 값이 가장 작은 노드
💡 힙에서 부모 노드는 자식 노드보다 우선 순위가 높다.
형제 노드끼리는 딱히 이런 관계가 없다.
💡 시간복잡도:
O(logN)
🔷 삽입
- 새로운 값을 삽입할 자리를 찾아 확장한다.
- 확장한 자리에 원소를 저장한다.
- 새로운 원소와 부모 노드를 비교하여 교체한다. (최대 힙이라면 더 큰 원소가 부모, 최소 힙은 반대)
- 더 올라갈 수 없을 때(비교할 부모 노드가 없을 때)까지 교체한다.
🔷 삭제
- 힙에서는 루트 노드의 원소만을 삭제할 수 있다.
- 루트 노드의 원소를 삭제하여 반환하는데, 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.
- 삭제 후 마지막 자리의 노드를 루트 노드로 가져온다.
- 자식 노드와 비교하며 힙의 종류에 따라 더 크거나 작은 자식을 더 비교할 노드가 없을 때까지 교체한다.
import java.util.Arrays;
// 부등호 방향을 바꾸면 최소힙이 된다.
// 힙 push시의 값과 꺼낼 때의 값의 부호를 반대로 바꾸어도 최소힙이 된다.
// 한번에 넣고 한번에 꺼내면 정렬된 모습을 얻을 수 있으며 이는 정렬힙
public class dailyClass {
// N개 힙이면 N+1의 사이즈로 완전이진트리 제작 (인덱스 0은 버리기 때문)
static int [] heap = new int[100];
static int heapSize = 0;
public static void main(String[] args) {
heapPush(5);
System.out.println(Arrays.toString(heap));
heapPush(30);
System.out.println(Arrays.toString(heap));
heapPush(17);
System.out.println(Arrays.toString(heap));
heapPush(127);
System.out.println(Arrays.toString(heap));
heapPush(54);
System.out.println(Arrays.toString(heap));
heapPush(6);
System.out.println(Arrays.toString(heap));
System.out.println(heapPop());
System.out.println(Arrays.toString(heap));
System.out.println(heapPop());
System.out.println(Arrays.toString(heap));
System.out.println(heapPop());
System.out.println(Arrays.toString(heap));
}
// 삽입
public static void heapPush(int item) {
heap[++heapSize] = item;
int ch = heapSize; // 자식
int p = ch/2; // 부모
while(p > 0 && heap[ch] > heap[p]) {
int tmp = heap[p];
heap[p] = heap[ch];
heap[ch] = tmp;
// 부모 자식을 한 레벨 위로 설정
ch = p;
p = ch /2;
}
}
// 삭제: 반환 타입을 heap으로 관리하고 있는 것의 타입으로 잡는다
public static int heapPop() {
// 공백 검사
if(heapSize <= 0) return -1;
int item = heap[1]; // 루트 반환
heap[1] = heap[heapSize--]; // 마지막 값 루트에 씌우기
int p = 1;
int ch = p * 2; // 왼쪽 자식
// 오른쪽 자식이 있을 때
if(ch + 1 <= heapSize && heap[ch] < heap[ch+1]) {
ch+=1; // 오른쪽 자식이 더 크면 오른쪽 자식으로 변경
}
while(ch <= heapSize && heap[p] < heap[ch]) {
int tmp = heap[p];
heap[p] = heap[ch];
heap[ch] = tmp;
p = ch;
ch = p * 2;
}
return item;
}
}
🔷 우선순위 큐 구현
-
노드 하나의 추가 / 삭제의 시간 복잡도가 O(logN)이고 최댓값 / 최솟값을 O(1)에 구하기 때문에 우선순위 큐를 구현하는 가장 효율적인 방법이 힙이다.
-
배열을 통해 트리 형태를 쉽게 구현할 수 있다.
💡 java에서는 priority queue를 제공해주고 있다.
import java.util.Collections;
import java.util.PriorityQueue;
public class PQTest {
public static void main(String[] args) {
// 우선순위 큐 클래스, 최소힙의 모습을 띠고 있다.
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 추가
pq.offer(100);
pq.add(20);
pq.add(62);
pq.add(16);
System.out.println("우선순위 큐로 보는 최소힙");
while(!pq.isEmpty()) {
// 꺼내기
System.out.println(pq.poll());
}
System.out.println();
// 최대힙으로 변환
PriorityQueue<Integer> pq2 = new PriorityQueue<>();
// 추가
pq2.offer(-100);
pq2.add(-20);
pq2.add(-62);
pq2.add(-16);
System.out.println("우선순위 큐로 보는 최대힙");
while(!pq2.isEmpty()) {
// 꺼내기
System.out.println(-pq2.poll());
}
System.out.println();
// 최대힙으로 변환하는 또 다른 방법
PriorityQueue<Integer> pq3 = new PriorityQueue<>(Collections.reverseOrder());
// 추가
pq2.offer(100);
pq2.add(20);
pq2.add(62);
pq2.add(16);
System.out.println("우선순위 큐로 보는 다른 최대힙");
while(!pq2.isEmpty()) {
// 꺼내기
System.out.println(pq2.poll());
}
}
}
🖥 응용 드가자
// 비교기준 작성
public class Person implements Comparable<Person> {
private String name;
private int age;
public Person() {}
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}
@Override
public int compareTo(Person o) {
// return this.age - o.age; // 나이 순 정렬
return this.name.compareTo(o.name); // 이름 순 정렬
}
}🖥 comparable 응용을 통한 정렬
import java.util.PriorityQueue;
public class PersonPQtest {
public static void main(String[] args) {
PriorityQueue<Person>pq = new PriorityQueue<>();
pq.offer(new Person("박영규", 25));
pq.offer(new Person("박영감", 85));
pq.offer(new Person("박영맨", 15));
pq.offer(new Person("박영차", 44));
pq.offer(new Person("박영순", 34));
pq.offer(new Person("박영고", 90));
while(!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
}
🖥 추상클래스로 comparator 구현해서 정렬
import java.util.Comparator;
import java.util.PriorityQueue;
public class PersonPQtest {
public static void main(String[] args) {
// 익명클래스: 객체를 한번만 생성
PriorityQueue<Person>pq = new PriorityQueue<>(new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
if(o1.age == o2.age) {
return o1.name.compareTo(o2.name);
}
return o1.age - o2.age;
}
// 나이 순 정렬을 하다 같은 나이가 들어오면 이름 순 정렬
});
pq.offer(new Person("박영규", 25));
pq.offer(new Person("박영맨", 15));
pq.offer(new Person("박영차", 44));
pq.offer(new Person("박영순", 34));
pq.offer(new Person("박영고", 90));
pq.offer(new Person("박영감", 90));
while(!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
}
🔷 힙 정렬
- 이진 트리와 유사한 방법으로 수행하며 배열에 저장된 자료를 정렬하기에 유용하다.
- 정렬을 위한 2단계
1) 하나의 값을 힙에 삽입한다. (반복)
2) 힙에서 순차적(오름차순)으로 값을 하나씩 제거한다.
💡 시간복잡도
삽입:O(logN)
삭제:O(logN)
전체 정렬:O(NlogN)
Hodie mihi, Cras tibi