힙 (Heap)
2019. 4. 1. 17:12한마디로 정의
완전이진트리 자료구조를 기반한 부모와 자식노드 만이 대소 관계가 성립하는 자료형이야. (자식노드 끼리는 X)
설명
힙은 큰 key(우선순위)에 자주 엑세스하거나 키 중심으로 정렬된 시퀀스를 활용해야할 때 유용해
기능은 주로 3개의 기능이 쓰여
삽입(새로운데이터 추가)
조회(루트노드 조회) (제일 큰 값 혹은 작은 값이 들어가 있을거야)
삭제(루트노드 삭제)
맨 마지막에 원소를 넣고, 형제와 부모노드를 비교해서 셋 중에 큰 값을 부모로 교체해. Heap을 재조정하는 거지 Heap의 높이만큼의 연산이 필요해. 여기서 재조정은 형제 노드, 부모 노드와 비교해서 셋 중에 큰 값을 부모노드로 만들어. 그리고 그 부모 노드도 똑같은 연산을 해서 루트노드까지 진행해
하나의 데이터 삽입연산 시간복잡도 O(logN)
최대원소를 제거 후 깨진 Heap구조를 재조정하는데 O(logN) 연산이 들어. 자식노드 둘 중에 큰 값을 갖고 올라와. 그것을 맨 아래까지 진행해. 삭제 연산도 Heap의 높이만큼의 부모 교환이 이루어지지 그래서
하나의 데이터 삭제연산 시간복잡도 O(logN)
맨 처음원소가 제일 키 값이 큰 것일 거야
조회연산 시간복잡도 O(1)
따라서 N개의 데이터를 삽입, 삭제연산을 할 때 O(NlogN) 시간복잡도가 들어
주의해야할 것은 힙은 탐색의 용도가 아니라는 점이야
어떤 값을 탐색하고 싶으면 이진트리로 된 자료구조를 쓰는 것이 좋고
큰 키를 자주 엑세스하고 싶으면 힙을 쓰는게 좋아
제일 꼭대기가 키값이 큰 것이 Max heap !
제일 꼭대기가 키값이 작은 것이 Min heap !
(번외)
최대원소 제거 후 Heap 구조를 재조정하는 연산이 배열을 전체적으로 다 훑고 지나가므로 참조지역의 특성을 활용한 캐시의 성능가속을 얻기 어려워(부모와 자식의 index가 서로 가깝게 있지 않아) 그래서 어떤 배열을 정렬할 때 퀵정렬을 많이써. 그대신 우선순위 큐에는 힙이 가장 적당하지.
구현
개념은 완전이진트리이니까 완전이진트리를 구현할 수 있는 데이터타입으로 구현하면 돼
가장 대중적인 ArrayList 방법을 써.
왼쪽자식 = 부모 * 2
오른쪽자식 = 부모 * 2 + 1
부모 = 해당인덱스 / 2
이렇게 빠르게 접근할 수 있어서 ArrayList 방법을 써
동작과정
위 링크를 참조하면 좋을거 같아
어디에 쓰일까
우선순위 큐
힙정렬
다음 문제를 풀면 도움이 될거야
최소힙 구현 문제
https://www.acmicpc.net/problem/1927
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// 왼쪽자식 = 부모 * 2
// 오르쪽자식 = 부모 * 2 + 1
// 부모 = 자식 / 2
//9
//0
//12345678
//1
//2
//0
//0
//0
//0
//32
//12
//1
//6
//5
//4
//3
//2
//0
//0
//0
//0
//0
//0
// 최소힙을 구현할 예정
class Heap {
int[] heap;
int len;
public Heap() {
heap = new int[100000];
heap[len++] = 0; // 첫번째는 쓰지 않는다.
}
public void insert(int n) {
heap[len++] = n;
int p = len - 1; // p는 현재 추가된 위치
// 새로들어온애가 부모보다 더 작다면 바꾼다. 왜냐면 최소힙을 구현하려고
// 새로들어온 애를 부모로 바꾼다.
while (p < 1 || heap[p / 2] > heap[p]) {
// 부모노드와 자식 노드의 값 교환
int tmp = heap[p / 2];
heap[p / 2] = heap[p];
heap[p] = tmp;
p = p / 2; // 새로들어 온 애는 부모가 될 것이므로 p를 부모로 초기화
}
}
public int delete() {
if (len <= 1)
return 0;
int deleteItem = heap[1]; // 삭제할 노드 = 루트노드
// 일단 처음에
heap[1] = heap[len - 1];
// heap.remove(len - 1);
len--; // 하나를 삭제한다.
int pos = 1;
while ((pos * 2) < len) {
int min = heap[pos * 2];
int minPos = pos * 2;
if (((pos * 2 + 1) < len) && min > heap[pos * 2 + 1]) {
min = heap[pos * 2 + 1];
minPos = pos * 2 + 1;
}
if (heap[pos] < min)
break;
// 부모노드 자식노드 교환
int tmp = heap[pos];
heap[pos] = heap[minPos];
heap[minPos] = tmp;
pos = minPos;
}
return deleteItem;
}
}
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
Heap heap = new Heap();
for (int i = 0; i < n; i++) {
int data = in.nextInt();
if (data == 0) {
System.out.println(heap.delete());
} else {
heap.insert(data);
}
}
}
}