---

⚡ Tree (2)

---

📌 수식 트리

🔷 수식을 표현하는 이진 트리

• 수식 이진트리라고 부르기도 한다.
• 연산자는 루트 노드이거나 가지 노드
• 피연산자는 모두 리프 노드

---

📌 힙(Heap)

🔷 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조

1. 최대 힙(max heap)

• 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
• 부모 노드의 키 값 >= 자식 노드의 키 값
• 루트 노드: 키 값이 가장 큰 노드

2. 최소 힙(min heap)

• 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
• 부모 노드의 키 값 <= 자식 노드의 키 값
• 루트 노드: 키 값이 가장 작은 노드

💡 힙에서 부모 노드는 자식 노드보다 우선 순위가 높다.
형제 노드끼리는 딱히 이런 관계가 없다.

💡 시간복잡도: O(logN)

🔷 삽입

1. 새로운 값을 삽입할 자리를 찾아 확장한다.
2. 확장한 자리에 원소를 저장한다.
3. 새로운 원소와 부모 노드를 비교하여 교체한다. (최대 힙이라면 더 큰 원소가 부모, 최소 힙은 반대)
4. 더 올라갈 수 없을 때(비교할 부모 노드가 없을 때)까지 교체한다.

🔷 삭제

1. 힙에서는 루트 노드의 원소만을 삭제할 수 있다.
2. 루트 노드의 원소를 삭제하여 반환하는데, 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.
3. 삭제 후 마지막 자리의 노드를 루트 노드로 가져온다.
4. 자식 노드와 비교하며 힙의 종류에 따라 더 크거나 작은 자식을 더 비교할 노드가 없을 때까지 교체한다.

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)