🌱 힙(Heap)
🌿 Heap이란?
최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조입니다.
📌 완전 이진 트리(Complete Binary Tree)
마지막 노드를 제외한 모든 노드가 채워져있으면서 리프 노드가 왼쪽부터 채워진 노드를 말합니다. 여기서 추가로 리프 노드 외 모든 노드가 2개의 자식 노드를 갖게 되면 포화 이진 트리(perfect binary tree)가 됩니다.
- 조건
- 마지막 노드를 제외한 모든 노드가 채워져있어야 함
- 모든 노드들은 왼쪽부터 채워져있어야 함
🌿 Heap의 성능
숫자가 낮을수록 우선순위가 높다고 가정할 때 매 번 새 원소가 들어올 때마다 기존 노드들과 비교하고 정렬하는 비효율적인 작업을 하게 됩니다.
'부모 노드는 항상 자식 노드보다 우선순위가 높다.'
위 조건이 붙게 되면, 모든 요소들을 우선순위를 정할 필요 없이 부모 노드는 자식 노드보다 항상 우선순위가 앞선다는 조건만 만족시키며 완전이진트리 형태로 채워나가는 것입니다.
Root 노드는 항상 우선순위가 높은 노드입니다. 이러한 원리로 최댓값 혹은 최솟값을 빠르게 찾아낼 수 있다는 장점과 함께 삽입/삭제 연산 시에도 부모 노드가 자식 노드보다 우선순위만 높으면 되므로 결국 트리의 깊이 만큼만 비교를 하면 되기 때문에 매우 빠르게 수행할 수 있습니다.
탐색 : O(1)
삽입/삭제 : O(logN)
그리고 부모, 자식 관계만 신경쓰면 되기 때문에 형제 간 우선순위는 고려되지 않습니다. 이러한 정렬 상태를 흔히 '반 정렬 상태' 혹은 '느슨한 정렬 상태', '약한 힙(weak heap)' 이라고도 부릅니다.
🌿 Heap 종류
최소 힙 : 부모 노드의 값(key 값) <= 자식 노드의 값(key 값)
최대 힙 : 부모 노드의 값(key 값) >= 자식 노드의 값(key 값)
🌿 Heap 특징 및 성질
가장 표준적으로 구현되는 방식은 배열입니다. 연결리스트는 특정 노드의 검색, 이동 과정이 조금 더 번거롭지만 배열은 특정 인덱스에 바로 접근할 수 있어 좀 더 효율적입니다.
[특징]
1. 구현의 용이함을 위해 시작 인덱스는 1부터 시작
2. 각 노드와 대응되는 배열의 인덱스는 '불변' (아래 성질의 불변을 의미)
[성질]
1. Left child's index = Parent's index * 2
2. Right child's index = Parent's index * 2 + 1
3. Parent's index = child's index / 2
🌿 구현(최소힙)
최대힙은 compare() 또는 compareTo() 에서 조건을 0보다 같거나 크다로 바꿔주면 됩니다.
📌 노드 추가 - add()
위와 같은 작업을 위로 올라가면서 선별한다고 하여 sift-up(상향 선별) 이라고도 불립니다.
값을 추가할 때는 size+1 위치에 새로운 값을 추가하고 상향 선별 과정을 거쳐 '재배치'를 해주는 방식입니다. 이 때, 재배치 되는 노드를 타겟노드라고 생각하면 됩니다.
📌 노드 삭제 - remove()
삭제 연산의 경우 root에 있는 노드를 삭제하고, 마지막에 위치했던 노드를 root 노드로 가져와 add와는 반대로 자식노드가 재배치하려는 노드보다 크거나 자식노드가 없을 때까지 자신의 위치를 찾아가면 됩니다.
중요한 점은 왼쪽 자식 노드와 오른쪽 자식 노드 중 '작은 값을 가진 노드'와 재배치할 노드와 비교해야 합니다.
이렇게 아래로 내려가면서 재비치하는 과정을 sift-down(하향 선별)이라고도 합니다.
package heap;
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;
public class Heap<E> {
private final Comparator<? super E> comparator;
private static final int DEFAULT_CAPACITY = 10; //최소(기본) 용적 크기
private int size; //요소 개수
private Object[] array; //요소를 담을 배열
//생성자1 (초기 공간 할당x)
public Heap() {
this(null);
}
public Heap(Comparator<? super E> comparator) {
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.comparator = comparator;
}
//생성자2(초기 공간 할당o)
public Heap(int capacity) {
this(capacity, null);
}
public Heap(int capacity, Comparator<? super E> comparator) {
this.array = new Object[capacity];
this.size = 0;
this.comparator = comparator;
}
//받은 인덱스의 부모 노드 인덱스 반환
private int getParent(int index) {
return index / 2;
}
//받은 인덱스의 왼쪽 자식 노드 인덱스 반환
private int getLeftChild(int index) {
return index * 2;
}
//받은 인덱스의 오른쪽 자식 노드 인덱스 반환
private int getRightChild(int index) {
return index * 2 + 1;
}
/**
* @param newCapacity : 새로운 용적 크기
*/
private void resize(int newCapacity) {
Object[] newArray = new Object[newCapacity];
//copy array to newArray
for (int i = 1; i <= size; i++) {
newArray[i] = array[i];
}
/*
* 현재 배열은 GC 처리를 위해 null 처리
* 새 배열 연결
* */
this.array = null;
this.array = newArray;
}
public void add(E value) {
//배열 용적 Fulled -> Doubling
if (size + 1 == array.length) {
resize(array.length * 2);
}
siftUp(size + 1, value); //가장 마지막에 추가되는 위치와 타겟을 넘김
size++; //재배치 후 사이즈 증가
}
/**
* 상향 선별
*
* @param idx 추가할 노드의 인덱스
* @param target 재배치 할 노드
*/
private void siftUp(int idx, E target) {
//comparator가 존재할 경우 comparator 을 인자로 넘김
if (comparator != null) {
siftUpComparator(idx, target, comparator);
} else {
siftUpComparable(idx, target);
}
}
/**
* Comparator을 이용한 sift-up
*
* @param : 외부로부터 로직 주입
*/
@SuppressWarnings("unchecked")
private void siftUpComparator(int idx, E target, Comparator<? super E> comp) {
//root 노드보다 클 때까지만 탐색
while (idx > 1) {
int parent = getParent(idx); //삽입 노드의 부모노드 인덱스
Object parentVal = array[parent]; //부모노드 값
//타겟 노드 값이 부모노드보다 크면 반복문 종료
if (comp.compare(target, (E) parentVal) >= 0) {
break;
}
/*
* 부모노드가 자식노드보다 크므로
* 현재 삽입 될 위치에 부모노드 값으로 교체
* 타겟 노드의 위치를 부모노드의 위치로 변경
* */
array[idx] = parentVal;
idx = parent; //idx로 loop가 진행되므로 갱신
}
//최종적으로 삽입될 위치에 타겟 노드 값을 저장
array[idx] = target;
}
/**
* Comparable을 이용한 sift-up
*
* @param : 외부로부터 로직 주입x(Comparable 클래스 내부에서 처리)
*/
@SuppressWarnings("unchecked")
private void siftUpComparable(int idx, E target) {
//Comparable 시그니처는 매개변수가 1개이므로, target을 comp로 만듦
Comparable<? super E> comp = (Comparable<? super E>) target;
while (idx > 1) {
int parent = getParent(idx);
Object parentVal = array[parent];
if (comp.compareTo((E) parentVal) >= 0) {
break;
}
array[idx] = parentVal;
idx = parent;
}
array[idx] = comp;
}
@SuppressWarnings("unchecked")
public E remove() {
//만약 root가 비어 있을 경우 예외 던짐
if (array[1] == null) {
throw new NoSuchElementException();
}
E result = (E) array[1]; //삭제될 요소 임시 보관
E target = (E) array[size]; //타겟이 될 요소
array[size] = null; //타겟 노드를 비움
//삭제할 노드의 인덱스와 재배치할 타겟 노드 넘김
siftDown(1, target); //루트 노드가 삭제되므로 1을 넘김
return result;
}
/**
* @param idx 삭제할 노드의 인덱스
* @param target 재배치할 노드
*/
private void siftDown(int idx, E target) {
//comparator가 존재할 경우 comparator 을 인자로 넘김
if (comparator != null) {
siftDownComparator(idx, target, comparator);
} else {
siftDownComparable(idx, target);
}
}
/**
* Comparator을 이용한 sift-up
*
* @param : 외부로부터 로직 주입
*/
@SuppressWarnings("unchecked")
private void siftDownComparator(int idx, E target, Comparator<? super E> comp) {
array[idx] = null; //노드 삭제
size--;
int parent = idx; //삭제 노드의 위치 = 재배치가 시작되는 인덱스
int child; //교환될 자식 인덱스
// 왼쪽 자식 노드의 인덱스가 요소의 개수보다 작을 때까지 반복
while ((child = getLeftChild(parent)) <= size) {
int right = getRightChild(parent); //오른쪽 자식 노드 인덱스
Object childVal = array[child]; //왼쪽 자식 노드 인덱스
/*
* 왼쪽 자식이 오른쪽 자식보다 큰 경우
* 왼쪽 자식으로 비교를 할 것이므로 오른쪽 자식으로 교체
* */
if (right <= size && comp.compare((E) childVal, (E) array[right]) > 0) {
child = right;
childVal = array[child];
}
//재배치할 노드가 자식 노드보다 작을 경우 반복문 종료
if (comp.compare(target, (E) childVal) <= 0) {
break;
}
/*
* 재배치할 노드가 자식 노드보다 큰 경우
* 부모와 자식 노드 스왑
* */
array[parent] = childVal;
parent = child; //다음 비교를 위해 parent 갱신
}
//최종적으로 재배치되는 위치에 타겟 값을 넣음
array[parent] = target;
/*
* 요소의 개수가 전체 1/4 미만이 된 경우
* 용적 절반 감소시킴(단, Baseline = 최소 용적)
* */
if (array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
/**
* Comparable을 이용한 sift-up
*
* @param : 외부로부터 로직 주입x(Comparable 클래스 내부에서 처리)
*/
@SuppressWarnings("unchecked")
private void siftDownComparable(int idx, E target) {
//Comparable 시그니처는 매개변수가 1개이므로, target을 comp로 만듦
Comparable<? super E> comp = (Comparable<? super E>) target;
array[idx] = null;
size--;
int parent = idx;
int child;
while ((child = getLeftChild(parent)) <= size) {
int right = getRightChild(parent);
Object childVal = array[child];
if (right <= size && ((Comparable<? super E>) childVal).compareTo((E) array[right]) > 0) {
child = right;
childVal = array[child];
}
if (comp.compareTo((E) childVal) <= 0) {
break;
}
array[parent] = childVal;
parent = child;
}
array[parent] = comp;
if (array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
public int size() {
return this.size;
}
@SuppressWarnings("unchecked")
public E peek() {
if (array[1] == null) {
throw new NoSuchElementException();
}
return (E) array[1];
}
public boolean isEmpty() {
return size == 0;
}
public Object[] toArray() {
return Arrays.copyOf(array, size + 1);
}
}
📌 테스트 - 기본형 참조 타입
package heap;
import java.util.Random;
public class HeapApplication {
public static void main(String[] args) {
Heap<Integer> heap = new Heap<>();
Random rdm = new Random();
for (int i = 0; i < 15; i++) {
heap.add(rdm.nextInt(100));
}
System.out.print("내부 배열 상태 : ");
for (Object val : heap.toArray()) {
System.out.print(val + " ");
}
System.out.println();
System.out.print("힙 요소 뽑기 : \t");
while (!heap.isEmpty()) {
System.out.print(heap.remove() + " ");
}
}
}
📌 테스트 - 사용자 정의 클래스
heap1 -> 오름차순(default) -> Comparable 이용
heap2 -> 내림차순 -> Comparator 이용
package heap;
import java.util.Comparator;
import java.util.Random;
public class HeapApplication {
public static void main(String[] args) {
Heap<Student> heap1 = new Heap<>();
Heap<Student> heap2 = new Heap<>(comparator);
heap1.add(new Student("김", 85));
heap2.add(new Student("김", 85));
heap1.add(new Student("이", 73));
heap2.add(new Student("이", 73));
heap1.add(new Student("한", 91));
heap2.add(new Student("한", 91));
heap1.add(new Student("장", 61));
heap2.add(new Student("장", 61));
heap1.add(new Student("조", 82));
heap2.add(new Student("조", 82));
heap1.add(new Student("백", 53));
heap2.add(new Student("백", 53));
System.out.println("[Heap 1] : 이름순(같을 경우 점수 오름차순)");
while (!heap1.isEmpty()) {
System.out.println(heap1.remove());
}
System.out.println();
System.out.println("[Heap 2] : 점수 내림차순(같을 경우 이름순)");
while (!heap2.isEmpty()) {
System.out.println(heap2.remove());
}
System.out.println();
}
private static Comparator<Student> comparator = (o1, o2) -> {
//나이가 같다면 이름순
if (o1.point == o2.point) {
return o1.name.compareTo(o2.name);
}
return o2.point - o1.point; //점수 내림차순
};
private static class Student implements Comparable<Student> {
String name;
int point;
public Student(String name, int point) {
this.name = name;
this.point = point;
}
@Override
public int compareTo(Student o) {
//이름이 같다면 점수순 (오름차순)
if (this.name.compareTo(o.name) == 0) {
return this.point - o.point;
}
//이름순
return this.name.compareTo(o.name);
}
@Override
public String toString() {
return "이름 : " + name + "\t나이 : " + point;
}
}
}
