힙

힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전이진트리
이때 부모의 값이 자식보다 항상 작아도 힙이라고 함(부모와 자식 요소의 관계만 일정하면 됨)
즉, 힙은 최소힙과 최대힙 2가지가 있음

특징

• 힙은 반정렬 상태(완전히 정렬된 상태가 아님)
• 삽입 / 삭제는 O(logN)으로 매우 빠름
• 보통 배열을 사용한 우선순위 큐로 구현

구현

• 보통 배열을 사용한 우선순위 큐로 구현
• 1번째 인덱스로 시작하면 자식노드는 2, 2+1로 나타냄
• 마친가지로 자식노드에서의 부모노드 인덱스는 /2로 표현 가능

최소힙

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class MinHeap {
	public static class minHeap {
		
		private ArrayList<Integer> heap;
		
		// 힙 생성자
		public minHeap() {
			heap = new ArrayList<>();
			heap.add(0);
		}
		
		// 삽입
		public void insert(int val) {
			heap.add(val);
			int p = heap.size() - 1;
			
			// 힙 사이즈 - 1이 1보다 작아질 때까지 진행 -> root로 이동
			while(p > 1 && heap.get(p / 2) > heap.get(p)) {
				System.out.println("swap");
				// 부모보다 자식 노드가 더 작으면 바꿔야 함 (최소힙)
				int tmp = heap.get(p/2);
				heap.set(p/2, heap.get(p));
				heap.set(p, tmp);
				
				p = p / 2; // p는 부모 값으로 변경(부모 노드 인덱스로 이동)
			}
		}
		
		// 삭제
		public int delete() {
			// 힙 사이즈 - 1이 1보다 작으면 0 리턴
			if(heap.size() - 1 < 1) {
				return 0;
			}
			
			// 삭제할 노드는 루트 노드임
			int deleteItem = heap.get(1);
			
			// root에 가장 마지막 값 넣고 마지막 값 삭제
			heap.set(1, heap.get(heap.size() - 1));
			heap.remove(heap.size() - 1);
			
			int pos = 1;
			while((pos * 2) < heap.size()) {
				int min = heap.get(pos * 2);
				int minPos = pos * 2;
				
				if(((pos*2 + 1) < heap.size()) && min > heap.get(pos*2 + 1)) {
					min = heap.get(pos*2 + 1);
					minPos = pos * 2 + 1;
				}
				
				if(heap.get(pos) < min)
					break;
				
				// 부모 자식 노드 교환
				int tmp = heap.get(pos);
				heap.set(pos, heap.get(minPos));
				heap.set(minPos, tmp);
				pos = minPos;
			}
			
			return deleteItem;	
		}
	}
	
	public static void main(String[] args) throws Exception, IOException {
		System.out.println("start");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		minHeap heap = new minHeap();
		
		for(int i = 0; i<N; i++) {
			int val = Integer.parseInt(br.readLine());
			
			if(val == 0 ) {
				System.out.println(heap.delete());
			} else {
				heap.insert(val);
			}	
		}
	}
}

최대힙

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class MaxHeap {
	public static class maxHeap {
		
		private ArrayList<Integer> heap;
		
		// 힙 생성자
		public maxHeap() {
			heap = new ArrayList<>();
			heap.add(1000000); // 인덱스 1부터 시작하기 위함
		}
		
		// 삽입
		public void insert(int val) {
			heap.add(val);
			int p = heap.size() - 1;
			
			// 루트까지 이동, 자식노드가 더 크면 swap
			while(p > 1 && heap.get(p / 2) < heap.get(p)) {
				System.out.println("swap");
				int tmp = heap.get(p/2);
				heap.set(p/2, heap.get(p));
				heap.set(p, tmp);
				
				p = p / 2; // p는 부모 값으로 변경(부모 노드 인덱스로 이동)
			}
		}
		
		// 삭제
		public int delete() {
			// 힙 사이즈 - 1이 1보다 작으면 0 리턴
			if(heap.size() - 1 < 1) {
				return 0;
			}
			
			// 삭제할 노드는 루트 노드임
			int deleteItem = heap.get(1);
			
			// root에 가장 마지막 값 넣고 마지막 값 삭제
			heap.set(1, heap.get(heap.size() - 1));
			heap.remove(heap.size() - 1);
			
			int pos = 1;
			while((pos * 2) < heap.size()) {
				int max = heap.get(pos * 2);
				int maxPos = pos * 2;
				
				if(((pos*2 + 1) < heap.size()) && max < heap.get(pos*2 + 1)) {
					max = heap.get(pos*2 + 1);
					maxPos = pos * 2 + 1;
				}
				
				if(heap.get(pos) > max)
					break;
				
				// 부모 자식 노드 교환
				int tmp = heap.get(pos);
				heap.set(pos, heap.get(maxPos));
				heap.set(maxPos, tmp);
				pos = maxPos;
			}
			
			return deleteItem;	
		}
	}
	
	public static void main(String[] args) throws Exception, IOException {
		System.out.println("start");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		maxHeap heap = new maxHeap();
		
		for(int i = 0; i<N; i++) {
			int val = Integer.parseInt(br.readLine());
			
			if(val == 0 ) {
				System.out.println(heap.delete());
			} else {
				heap.insert(val);
			}	
		}
	}
}

이진정렬

• 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능

정렬 과정

첫번째

두번쨰

세번쨰

종료

탐색 실패시 시작 인덱스가 마지막 인덱스보다 큰 경우 탐색이 종료