<Heap?>
우선순위 큐가 바로 힙 구조를 주로 이용.
int와 primitive 타입으로만 구현 하는 것이 아닌 객체 타입도 사용 할 수 있음
'최소값 또는 최대값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'
1) Tree
부모 노드 -> 자기 자신과 연결된 노드중 자신보다 높은 노드 의미
자식 노드 -> 자기 자신과 연결된 노드중 자신보다 낮은 노드 의미
루트 노드 -> 뿌리 노드라고 함, 하나의 트리에선 하나만 존재 & 부모 노드 없음
단말 노드 -> 리프노드라고 함, 자식 노드가 없는 노드
내부 노드 -> 부모가 같은 노드
깊이(depth) -> 특정 노드에 도달하기 위해 거쳐야 하는 간선의 개수
레벨 -> 특정 깊이에 있는 노드들의 집합, 구현하는 사람에 따라 0 또는 1로 시작
차수 (degree) -> 특정 노드가 하위 노드와 연결된 개수
<이진트리>
트리 구조에서 특정한 형태로 제한, 모든 노드의 최대 차수를 2로 제한 = 이진 트리
<완전 이진 트리>
마지막 레벨을 제와한 모든 노드가 채워져있으면 모든 노드가 왼쪽 부터 채워져 있어야 한다.
1) 마지막 레벨을 제외한 모든 노드가 채워져 있어야 한다.
2) 모든 노드들은 왼쪽 부터 채워져있어야 한다.
<포화 이진 트리>
마지막 레벨을 제외한 모든 노드는 두 개의 자식 노드를 갖는다.
<Heap 구현>
예시) 어떤 리스트에 값을 넣었다가 뺄때, 우선순위가 높은 것 부터 빼내려고 한다면, 숫자가 낮을 수록 우선 순위가 높다고 가정, -> 새로운 원소가 들어올때 마다 이미 리스트에 있던 원소들과 비교
- 부모 노드는 항상 자식 노드보다 우선순위가 높다.
=> 완전이진트리를 완성
루트노드는 항상 우선순위가 높은 노드, 최대값 혹은 최소값을 빠르게 찾아낼 수 있따.
장점: O(1)과 함께 삽입 삭제 연산에도 부모 노드가 자식 노드보다 우선순위만 높으면 결국 트리 깊이만큼만 비교 O(logN)의 시간복잡도를 갖아 빠르게 실행 가능.
참고) 형제 간 순위는 고려 x
이러한 정렬 상태를 반 정렬 상태, 느슨한 정렬 상태, 약한 힙
<Heap 종류>
정수나 문자의 경우 낮은 값이 높은 값 보다 우선
3,1,6,4 -> ,1,3,4,6
최소 힙: 부모의 노드(key 값) <= 자식의 노드(key 값)
최대 힙: 부모의 노드(key 값) => 자식의 노드(key 값)
최소힙 구현 (최대 힙의 경우 비교연산자만 변경)
표준적으로 구현되는 방식은 배열
연결리스트로도 구현은 가능 하지만, 이동, 검색 과정이 복잡
배열로 나타낸 그림
1) 구현이 용이하고, 인덱스는 1부터 시작
2) 각 노드와 대응되는 배열의 인덱스는 불편
3) 성질
-> 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2
-> 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2 + 1
-> 부모 노드 인덱스 = 자식 노드 인덱스 /2
<Heap 클래스 및 생성자 구현>
import java.util.Comparator;
public class Heap<E> {
private final Comparator<? super E> comparator;
private static final int DEFAULT_CAPACITY = 10; // 최소(기본) 용적 크기
private int size; // 요소 개수
private Object[] array; // 요소를 담을 배열
// 생성자 Type 1 (초기 공간 할당 X)
public Heap() {
this(null);
}
public Heap(Comparator<? super E> comparator) {
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.comparator = comparator;
}
// 생성자 Type 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;
}
}comparator = 객체를 정렬하고자 할 때, 임의의 순서로 정렬하고 싶을때 사용
DEAFULT_CAPACITY = 배열의 기본 및 최소 용적, 요소를 담을 배열의 크기를 의미
<resize 메소드 구현>
자료구조는 동적으로 만들 수 있어야 함
배열에 요소들이 모두 차면 배열의 크기를 늘려야 함.
이는 배열의 크기를 재조정 하기 위함
private void resize(int newCapacity) {
// 새로 만들 배열
Object[] newArray = new Object[newCapacity];
// 새 배열에 기존에 있던 배열의 요소들을 모두 복사해준다.
for(int i = 1; i <= size; i++) {
newArray[i] = array[i];
}
/*
* 현재 배열은 GC 처리를 위해 null로 처리한 뒤,
* 새 배열을 연결해준다.
*/
this.array = null;
this.array = newArray;
}새 배열을 생성, 기존에 있었던 배열의 요소들 복사, 새 배열을 가르키도록 새롭게 연결
다음은 Heap add에 대해 추가적으로 적겠다.
