지료구조 ) Java Heap 구현

• 완전 이진 트리구조의 자료구조
• 최대값, 최솟값을 기준으로 최대 힙, 최소 힙으로 구분된다.
• 최대 값
• 부모노드 >= 자식노드
• 최소 값
• 부모노드 <= 자식노드
• 연산
• 삽입
• 새로운 노드는 트리의 가장 마지막 노드로 삽입된다
• 부모 노드들과 비교 및 교환하여 힙의 성질을 만족.
• 삭제
• 루트노드를 삭제
• 비어있는 루트노드에 마지막 노드가 삽입된다.
• 루트노드부터 자식노드와 비교 및 교환하여 힙의 성질을 만족
• 인덱스 관계
• 부모인덱스 = 자식 인덱스 / 2
• 왼쪽 자식 인덱스 = 부모인덱스 * 2
• 오른쪽 자식 인덱스 = 부모인덱스 * 2 + 1
   
• java에서 배열을 이용하여 구현한 MinHeap
• min, max 힙 구현을 위한 힙 추상클래스

public abstract class Heap<T> {

 

protected T[] heap;

protected int size;

 

public abstract void insert(T n);

 

public abstract T delete();

 

}

 

• min Heap class

import java.util.ArrayList;

 

public class MinHeap extends Heap<Integer> {

 

public MinHeap() {

this.heap = new Integer[100];

this.size = 0;

}

 

@Override

public void insert(Integer n) {

 

if(heap.length == this.size) {

System.out.print("용량 부족");

return;

}

 

heap[++size] = n; //새로운노드를 끝에 삽입

 

int cIdx = size; //현재 노드를 가르키는 인덱스를 맨 뒤의 노드로 설정

 

while(cIdx > 1 && heap[cIdx] < heap[cIdx/2]) { //노드들을 비교 및 스왑

int tmp = heap[cIdx];

heap[cIdx] = heap[cIdx/2];

heap[cIdx/2] = tmp;

cIdx = cIdx / 2;                

}        

}

 

@Override

public Integer delete() {

int deleteItem = heap[1]; //제거할 노드를 리턴하기 위해 저장

 

heap[1] = heap[size]; // 맨 뒤의 노드를 맨처음으로 이동

heap[size--] = null; //맨 뒤의 노드를 null로 변경 및 사이즈 감소하여 제거

 

int cIdx = 1; //현재노드를 가르키는 인덱스

while(cIdx*2 < size) {

int next = cIdx*2; //현재를 기준으로 다음 자식들의 인덱스를 가르키는 변수

 

if(next+1 <= size && heap[next] > heap[next+1]) { //자식들을 비교하여 더 작은 자식과 비교

next++;

}

 

if(heap[next] < heap[cIdx]) {

int tmp = heap[cIdx];

heap[cIdx] = heap[next];

heap[next] = tmp;

}

else

break; //자식들보다 내가 더 작거나 같다면 break

 

cIdx = next; //현재 노드를 다름 노드로 변경.

 

}

return deleteItem;

}

}