데이터간에 순서가 보장되지 않음 ex) 2, 3, 4, 1, 5 추가 후 iterator를 이용해 출력 시 1, 2, 4, 3, 5로 출력
구현방법 및 특징 - 배열 기반으로 구현 1) 인덱스로 데이터에 바로 접근할 수 있음 2) 데이터의 삽입/삭제에서 데이터들을 한칸씩 뒤로 밀거나 당기는 연산이 있어야 함 3) 삽입의 위치를 찾아내기 위해 최악의 경우 배열의 모든 데이터들과 우선순위를 비교해야 함 4) 저장 시 시간복잡도 O(n), 삭제 시 시간복잡도 O(1)
- 연결리스트 기반으로 구현 1) 삽입의 위치를 찾기위해 최악의 경우 리스트의 모든 데이터와 우선순위를 비교해야 함 2) 저장 시 시간복잡도 O(n), 삭제 시 시간복잡도 O(n)
- 힙(heap)을 이용한 구현 1) 완전 이진트리의 형태 2) 단말노드에서 루트노드로 갈수록 값이 커지는 것을 최대 힙 (max heap) 이라고 하며 그 반대는 최소 힙 (min heap) 이라고 함 3) 저장 시 시간복잡도 O(logN), 삭제 시 시간복잡도 O(logN)
4) 형제노드끼리의 대소관계는 정해지지 않음
힙의 구현 (최대 힙 기준) 방법
힙도 마찬가지로 배열과 연결리스트로 구현 가능
그러나 배열로 구현하는 것이 일반적 (리스트로 구현할 경우 특정노드에 접근하거나 데이터 저장 시 마지막 위치를 알기 어렵기 때문)
데이터 저장 1) 완전 이진 트리르 ㄹ만족하는 마지막 위치에 데이터 저장 2) 부모노드와 대소관계 비교 후 부모노드의 값이 더 클 경우 교환하는 과정을 반복 (최대 힙 기준) 3) 아래는 데이터 10, 5, 7, 1 순으로 저장된 트리에 8을 저장한 그림
데이터 삭제 1) 데이터의 루트노드 삭제 2) 루트노드의 빈 공간은 마지막 노드를 루트노드로 설정 3) 자식노드들과 비교하며 더 큰 자식노드와 교환
노드마다 인덱스 값 부여
구현의 편의 상 인덱스는 1번부터 적용
노드의 인덱스 값 구하기 - 완전 이진 트리의 특성 때문에 아래와 같이 수식화 할 수 있음 - 아래 수식의 결과값들은 모두 정수 형태 (5 / 2 => 2) 1) 왼쪽 자식노드의 인덱스 값 : 부모노드의 인덱스 값 * 2 2) 오른쪽 자식노드의 인덱스 값 : 부모노드의 인덱스 값 * 2 + 1 3) 부모노드의 인덱스 값 : 자식노드의 인덱스 값 / 2
힙 구현
추상자료형 (ADT)
자료형
반환값
내용
Initialize()
void
힙 초기화
initialize(comparator)
void
힙 초기화 (비교함수 외부 등록)
isEmpty()
boolean
힙이 비어있는지 확인
compareHighChild(index)
int
자식노드 중 누가 더 우선순위가 높은지 반환
add(Data)
void
힙에 데이터 추가
remove()
Data
데이터 삭제
getParent(index)
int
부모노드의 위치값 반환
getLChild(index)
int
왼쪽 자식노드의 위치값 반환
getRChild(index)
int
오른쪽 자식노드의 위치값 반환
핵심기능 - 데이터 추가 : 마지막 위치에 데이터를 저장한 후 부모노드와 우선순위를 비교해서 자신이 어디에 위치해야 하는지 찾음 - 데이터 삭제 : 힙의 루트노드를 지우고 그 위치에 마지막 노드를 올린 후 자식노드와 비교하며 자신이 어디에 위치해야 하는지 찾음
구현
[ArrayHeap.java]
package Heap.ArrayList;
import java.util.Comparator;
public class ArrayHeap<E> {
private int MAX_CAPACITY = 5;
// 외부에서 정렬 방법 설정을 위한 변수
private Comparator<? super E> comparator = null;
// 내부에서 사용할 정렬을 위한 변수
private Comparable<? super E> comp = null;
private Object[] heap = null;
private int dataCount = 0;
public void init(int capacity) {
MAX_CAPACITY = capacity;
heap = new Object[MAX_CAPACITY + 1];
dataCount = 0;
}
public void init(int capacity, Comparator<? super E> comparator){
MAX_CAPACITY = capacity;
heap = new Object[MAX_CAPACITY + 1];
dataCount = 0;
this.comparator = comparator;
}
// index의 두 개의 자식 중 더 높은 놈 반환
private int compareHighChild(int index) {
// 자식이 없을 때
if (getLChild(index) > dataCount) {
return 0;
}
// 자식이 한 개
// 이진트리이므로 왼쪽부터 채워지기 때문에 왼쪽 자식노드만 확인
else if (getLChild(index) == dataCount) {
return getLChild(index);
}
// 자식이 두 개
else {
int lChild = getLChild(index);
int rChild = getRChild(index);
if (comparator == null) {
comp = (Comparable<? super E>)heap[lChild];
if (comp.compareTo((E)heap[rChild]) < 0) {
return lChild;
}
else {
return rChild;
}
}
else {
if (comparator.compare((E) heap[lChild], (E) heap[rChild]) < 0) {
return lChild;
}
else {
return rChild;
}
}
}
}
public boolean isEmpty() {
if (dataCount == 0){
return true;
}
return false;
}
// 마지막 위치에 데이터를 저장한 후 부모노드와 우선순위를 비교해서 자신이 어디에 위치해야 하는지 찾음
public void add(E data) {
if (dataCount > MAX_CAPACITY) {
System.out.println("저장 공간이 부족합니다.");
return;
}
int index = dataCount + 1;
while (index != 1){
if (comparator == null) {
// 부모노드와 우선순위 비교
comp = (Comparable<? super E>) data;
// 자식노드의 우선순위가 더 낮은 경우
if (comp.compareTo((E)heap[getParent(index)]) >= 0){
break;
}
}
else {
// 부모노드와 우선순위 비교
// 자식노드의 우선순위가 더 낮은 경우
if (comparator.compare(data, (E)heap[getParent(index)]) >= 0){
break;
}
}
// 자식노드가 더 우선순위가 높으므로 부모노드를 자식노드와 swap함
heap[index] = heap[getParent(index)];
index = getParent(index);
}
dataCount++;
heap[index] = data;
}
// 힙의 루트노드를 지우고 그 위치에 마지막 노드를 올린 후 자식노드와 비교하며 자신이 어디에 위치해야 하는지 찾음
public E remove() {
E removeData = (E)heap[1];
heap[1] = null;
int lastIndex = dataCount;
int childIndex = 0;
int parentIndex = 1;
while((childIndex = compareHighChild(parentIndex)) > 0) {
if (comparator == null) {
comp = (Comparable<? super E>)heap[lastIndex];
if (comp.compareTo((E)heap[childIndex]) < 0){
break;
}
}
else {
if (comparator.compare((E)heap[lastIndex], (E)heap[childIndex]) < 0){
break;
}
}
heap[parentIndex] = heap[childIndex];
parentIndex = childIndex;
}
heap[parentIndex] = heap[lastIndex];
heap[lastIndex] = null;
dataCount--;
return removeData;
}
private int getParent(int index) {
return index / 2;
}
private int getLChild(int index) {
return index * 2;
}
private int getRChild(int index) {
return index * 2 + 1;
}
public void printAll() {
for(E e : (E[])heap) {
if (e == null) {
continue;
}
System.out.println(e);
}
}
}
