About BinaryHeap

차근차근 여러가지 자료 구조들을  하나씩 소개해볼까 한다.

 

우선순위 큐?

우선순위 큐(priority queue)는 자료 구조의 한 종류로서, 큐(queue)와 트리(tree) 두 개념 모두와 관련이 있다.

구체적으로 설명하자면:

 

큐와의 관계

큐(queue)는 FIFO(First In, First Out) 방식으로 작동하는 자료 구조다.

즉, 먼저 들어온 요소가 먼저 나가는 구조인데 .우선순위 큐는 큐의 특수한 형태로, 각 요소가 우선순위를 가지며, 요소가 들어온 순서가 아니라 우선순위에 따라 나가는 방식이다. ( 들어온 순서가 아닌 우선순위를 매기는 방식)

우선순위가 높은 요소가 먼저 나갑니다.

따라서, 우선순위 큐는 큐의 개념을 확장한 것으로 볼 수 있다.

트리와의 관계

우선순위 큐는 내부적으로 다양한 자료 구조를 사용하여 구현될 수 있는데 그 중 하나가 힙(heap)입니다.

힙은 트리 자료 구조의 일종으로,

특히 이진 힙(binary heap)은 완전 이진 트리 형태 +  부모 노드가 자식 노드보다 높은(최대 힙) 또는 낮은(최소 힙) 우선순위를 가집니다.따라서, 우선순위 큐는 트리(특히 힙)를 사용하여 구현되는 경우가 많습니다.

결론

우선순위 큐는 큐의 특수한 형태이면서도, 트리(특히 힙)를 사용하여 효율적으로 구현될 수 있다. 따라서,

우선순위 큐는 큐의 일부로 볼 수 있지만 그 내부 구현은 트리와 깊은 관련이 있습니다. 

 

탄생 배경

스택 큐는 삽입 항목이 임의의 우선순위를 가지려면 새 항목 삽입때마다 저장항목들을 우선순위에 따라 정렬해야 하는 비효율이 발생한다. 먼저꺼내던가 나중에 꺼내던가 이 둘 밖에 없으니까...

 

구현 : 완전이진트리의 구현과 1차원 배열

1. 먼저 첫번째 원소는 비워둔다. a[0]은 사용하지 않아.
2. 레벨순회 순으로 a[1]부터 저장한다. 완전이진트리이므로 쭉쭉 차겠다.

우선순위 큐는 삽입시 정렬이 필요 없으며 , 가장 높은 우선순위 항목의 접근 및 삭제를 o(1) 시간에.. 개사기라고 볼 수 있다.

 

 

 

구현 : 완전이진트리의 구현과 1차원 배열

1. 먼저 첫번째 원소는 비워둔다. a[0]은 사용하지 않아.
2. 레벨순회 순으로 a[1]부터 저장한다. 완전이진트리이므로 쭉쭉 차겠다.

삭제 연산 : 최솟값 삭제

만약 최소 힙 일 경우, 루트노드가 가장 작은 키의 값을 지니겠다.

근데 내가 최솟값을 삭제한다 가정하면 .. 루트 노드가 삭제되며 가장 마지막 배열에 저장되어 있는 놈이 루트노드로 대체

왜 이런 방식으로 하는가?

1차원배열의 특성상 중간에 있는 놈을 첫번쨰 인덱스로 옮기면 다른 인덱스를 한번에 옮겨줘야한다.

따라서 마지막 노드, 첫번째 노드 둘의 변화만 있는게 제일 효율적

삽입 연산 : 새 노드를 맨 마지막 인덱스로.

힙의 마지막 노드의 다음 노드로 insert한다. 이 노드가 어떤 값을 노드인지 모르기 때문에 루트 방향으로 올라가면서 자기가 여기 있는게 맞는지를 확인한다.

 

이렇게 배열의 값들을 삭제 삽입하는것 보단 swap을 하는것이 시간적으로 훨씬 효율적이기 때문에 이 방식을 택한다.

삭제해버리면 빈자리를 다 채워줘야하니 시간적으로 여유가 없다.

 

 

코드 구현 (배열로 이진힙으로 구현한다.)

Entry Class — similar with Node

이진힙의 노드라고 생각하면 편하다.

• Key, Value의 타입을 제네릭화 시킨다. (비교의 대상)
• instance 변수로는 key, value 가 있다.
• entry class

public class Entry<Key extends Comparable<Key>, Value>{
	private Key key
	private Value value
	
	Getter & Setter
}

BHeap Class -

인스턴스 변수 - binary heap을 구성할 배열 + 힙의 크기인 size

public class BHeap <Key extends Comparable<Key>,Value>{
	private Entry[] arr;
	private int size;
	
	public BHeap(Entry[] arr, int size){
		this.arr =arr;
		this.size =size;
	}

}

메서드 : size, greater, swap , createheap, insert, deleteMin, downheap + upheap

size

greater - 키값의 대소비교

private boolean greater(int x, int y){
	return a[j].getKey().compareTo(a[i].getKey())<0
}

swap

private void swap(int x, int y){
	Entry tmp = arr[x];
	arr[x]=arr[y];
	arr[y] = tmp;
}

createHeap

private void createHeap(){
	for(int i=size/2; i>0; i--){
		downheap(i);
	}
}

downheap

private void downHeap(int i){
	while(size >= i*2){
	 int child_index = 2*i;
	 
	 //왼쪽 오른쪽 자식 크기비교
	 if(child_index > size && greater(child_index, child_index) {
			 //자식 놈들 중 큰 놈이랑 싸워야 함
		 child_index ++;
	 }
	 //즉 arr[i] (부모 노드) 가 더 작다면 굳이 뭐 더 할 필요가 없다.
	 if(!greater(i,child_index) -> break;
	 //아니라면, 값을 바꿔주고
	 swap(i,child_index);
	 // child index i로 바꿔주며, 다음 반복을 실행.
	 i=child_index; 

	}

}

insert

삽입할떄는 마지막 노드에다가 삽입한다. 그냥 마지막 노드에다가 삽입해버리면 힙 속성이 깨지기 마련이니

public void insert(Key key, Value value){
	Entry newValue = new Entry(key,value);
	size++;
	arr[size]= newValue;
	uphead(size);
}

uphead

private void uphead(int x){
	while(x>1 && greather(x,x/2)){
		swap(x,x/2)
		//base case
		x=x/2;
	}

}

deleteMin()

public Entry deleteMin(){
	Entry min = arr[1];
	swap(min, size);
	size--;
	arr[size+1] = null;
	downheap(1);
	
	return min;
}