[자료구조] 우선순위 힙 -2

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.: https://github.com/ejImDev/data_structure_study.git

연산

최솟값 삭제 (루트의 키를 삭제)
1. 힙의 가장 마지막 노드, 즉 배열의 가장 마지막 원소를 루트로 옮김
2. 힙의 크기를 -1로 감소
3. 루트로부터 자식들 중 작은 값을 가진 자식과 키를 비교하여 힙속성이 만족될 때까지 키를 교환하며 이파리 방향으로 진행 (= downHeap 이라고 부름)
삽입 연산
1. 힙의 마지막 노드. 즉, 배열의 마지막 원소의 바로 다음 빈 원소에 새로운 항목을 저장
2. 루트 방향으로 올라가면서 부모 노드의 키 값과 비교하여 힙 속성이 만족될 때까지 노드를 교환 (= upHeap 이라고 부름)

Entry 클래스

public class Entry <Key extends Comparable<Key>, Value> {
	private Key ky;
	private Value val;
	public Entry (Key newKey, Value newValue) {
		ky = newKey;
		val = newValue;
	}
	public Key getKey() { return ky; }
	public Value getValue() { return val; }
	public void setKey(Key newKey) { ky = newKey; }
	public void setValue(Value newValue) { val = newValue; }
}

이진힙 클래스

public class BHeap<Key extends Comparable<Key>, Value> {
	private Entry[] a; // a[0]은 사용 안함
	private int N; // 힙의 크기
	public BHeap(Entry[] harray, int initialSize) {
		a = harray;
		N = initialSize;
	}
	public int size() { return N; }
	private boolean greater(int i, int j) {
		return a[j].getKey().compareTo(a[i].getKey()) < 0; 
	}
	private void swap(int i, int j) {
		Entry temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

힙 생성 메소드

초기에 임의의 순서로 키가 저장되어있는 배열의 항목들을 최소힙으로 만드는 메소드
```
public void createHeap() {
  for(int i = N/2; i>0; i--){
      downHeap(i);
  }
}
```

downHeap()

private void downHeap(int i){
	while(2*i <= N) {
		int k = 2*i;
		if(k<N && greater(k, k+1)) { k++; }
		if(!greater(i, k)) { break; }
		swap(i, k);
		i = k;
	}
}

insert()

public void insert(Key newKey, Value newValue) {
	Entry temp = new Entry(newKey, newValue);
	a[++N] = temp;
	upHeap(N);
}

upHeap()

private void upHeap(int j) {
	while (j>1 && greater(j/2, j)){
		swap(j/2, j);
		j = j/2;
	}
}

deleteMin()

public Entry deleteMin() {
	Entry min = a[1];
	swap(1, N--);
	a[N+1] = null;
	downHeap(1);
	return min;
}

a[N/2+1]~a[N]에 대하여 수행하지 않은 이유 : 이 노드들 각각은 이파리노드이므로, 각 노드 스스로가 힙의 크기가 1인 최소힙이기 때문(비교할 노드가 없기 때문)

정리

insert, delete 연산을 위한 upHeap은 삽입된 노드나 키값이 작은 노드로부터 루트노드까지 올라가며 부모와 자식노드를 교환
delete_min 연산에서는 힙의 마지막 노드를 루트노드로 이동한 후, downHeap을 최하위 층의 노드까지 교환해야 하는 경우가 발생
힙에서 각 연산의 수행시간은 힙의 높이에 비례
힙은 완전이진트리이므로 힙에 N개의 노드가 있으면 그 높이는 log(N+1)
각 힙 연산의 수행시간은 O(logN)

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/PEZ_s_RywAg

IM

연산

Entry 클래스

이진힙 클래스

힙 생성 메소드

downHeap()

insert()

upHeap()

deleteMin()

정리