수식 트리 / 힙

수식 트리

• 수식을 표현하는 이진 트리
• 수식 이진 트리라고 부르기도 함
• 연산자는 루트 노드이거나 가지 노드(internal node)
• 피연산자는 모두 잎 노드(external node)

힙

• 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
• 최대힙
  • 부모 노드의 키 값>=자식 노드의 키 값
  • 루트 노드 : 키 값이 가장 큰 노드(최대 값)
  • 전체의 노드/2=부모의 노드 개수

• 최소힙
  • 부모 노드의 키 값<=자식 노드의 키 값
  • 루트 노드 : 키 값이 가장 작은 노드(최소 값)

삽입

삭제

• 힙에서는 루트 노드의 원소만을 삭제할 수 있다.
• 루트 노드의 원소를 삭제하여 반환된다.
• 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.

https://swexpertacademy.com/main/talk/solvingClub/problemPassedUser.do?contestProbId=AV-Tj7ya3jYDFAXr&solveclubId=AYWesuzK3nUDFAQK&problemBoxTitle=3%EC%A3%BC%EC%B0%A8&problemBoxCnt=5&probBoxId=AYaW02iKojQDFARM+

SW Expert Academy

package TEST1;

import java.util.Arrays;
import java.util.Scanner;

public class swea2930 {
	static int[] arr;
	static int lastidx;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int Tc = 1; Tc <= T; Tc++) {
			lastidx = 0;
			int n = sc.nextInt();
			arr = new int[n + 1];
			System.out.print("#" + Tc + " ");
			for (int i = 0; i < n; i++) {
				int c = sc.nextInt();
				switch (c) {
				case 1:
					int num = sc.nextInt();
					arr[++lastidx] = num;
					int cur = lastidx;
					while (arr[cur] > arr[cur / 2] && cur > 1) {
						swap(cur, cur / 2);
						cur = cur / 2;
					}

					break;

				case 2:
					if (lastidx == 0) {
						System.out.print("-1" + " ");
						break;
					}
					System.out.print(arr[1] + " ");
					arr[1] = arr[lastidx];
					arr[lastidx] = 0;
					lastidx--;
					int curr = 1;
					while (true) {
						int child = curr * 2;
						if (child + 1 <= lastidx && arr[child] < arr[child + 1])
							child++;
						if (child > lastidx || arr[child] < arr[curr])
							break;
						else swap(curr, child);
						curr= child;
//						System.out.println(child);
//						System.out.println(curr);
					}
					break;
				}
//				System.out.println(Arrays.toString(arr));
			}
			System.out.println();
		}
	}

	private static void swap(int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}