힙과 이진 정렬
힙
힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전이진트리
이때 부모의 값이 자식보다 항상 작아도 힙이라고 함(부모와 자식 요소의 관계만 일정하면 됨)
즉, 힙은 최소힙과 최대힙 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);
}
}
}
}
이진정렬
- 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능
정렬 과정
첫번째
두번쨰
세번쨰
종료
탐색 실패시 시작 인덱스가 마지막 인덱스보다 큰 경우 탐색이 종료
Author And Source
이 문제에 관하여(힙과 이진 정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jodmsoluth/힙과-이진-정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)