[ 알고리즘 ] 우선순위 큐 (2) - 힙

@ 궁금증

배열로 구현한 우선순위 큐가 너무 비효율적이라서 트리를 통해서 구현하는 방법을 공부해 보자

---

@ 공부

## 자료구조 힙

힙 이란?

부모의 값이 항상 자식보다 작은 완전 이진 트리

- 즉 부모일수록 우선 순위가 높다.

루트에 있는 값은 가장 우선 순위가 높은 값이 된다. ( 현재 예제에서는 숫자가 낮을 수록 우선 순위가 높은 것입니다. )

1) 추가

2) 제거는 어떻게 하는가?

## 완전 이진 트리 ( 높이 )

- 완전 이진 트리란? 

이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다. 이진 트리는 이진 탐색 트리 와 이진 힙의 구현에 흔히 쓰인다.

 

- 높이 구하기

 

[ 여기서 말하는 log 밑은 2가 됩니다. ]

노드가 n개 일때 logN 높이를 갖는다.

 

## 삽입 하는 방법

 

- 4를 추가한다면?

삽입은 완성 했지만 > 우선 순위가 옳지 않다.

제일 마지막에 넣는다!!

4 와 7 관계가 이상하다.  4와 7 사이 변경 한다.

 

- 1일 추가 한다면?

삽일을 생각할때 예를 들어 1을 추가 하게 되면 1은 5와 비교 하게 되고 3 과 비교 하게 되고 2와 비교 하게 됩니다

1 - 5, 1 - 3, 1- 2 ( 총 3번의 비교를 통해서 바뀐다. ) 

=> 삽입 시간 복잡도 O(logN) 만큼 걸립니다.

## 삭제 하는 방법

 

[ 삭 제 ]

4를 삭제 하고 

27을 루트에 넣는다.

27 - 5와 바꾼다.

27 - 7 과 바꾼다.

 

- 루트를 없애게 되면 완전 이진 트리 형태를 만족하지 못하게 됩니다.

- 그래서 제일 마지막에 있는 노드를 맨 위로 올려 줘야 완전 이진 트리 형태가 만족 하게 됩니다.

- 자식 중에서 우선 순위가 높은 것과 바꾸면서 자식이 없을 때 까지 내려 갑니다.

 

즉 삽입이나 삭제나 트리 높이 만큼 걸리게 됩니다. 

=> 삭제 시간 복잡도 O(lonN) 만큼 걸립니다.

 

즉 배열과 비교 했을때  엄청난 차이다 !!!!

lonN 은 엄청 작은 수다 !!!

---

@ 구현

public class Heap {
	public static void main(String[] args) {
		PriorotyHeap pHeap = new PriorotyHeap();
			pHeap.push(3);
			pHeap.push(5);
			pHeap.push(88);
	
		System.out.println(pHeap.top());
		pHeap.pop();
		System.out.println(pHeap.top());
		pHeap.pop();
		System.out.println(pHeap.top());
		pHeap.pop();
	}
}

class PriorotyHeap {
	int Max = 100;
	int[] data = new int[Max];
	int len = 1;

	void push(int value) {
		data[len++] = value;
		int valueInx = len - 1;

		while (valueInx > 1 && (data[valueInx] < data[valueInx / 2])) {
			int temp = data[valueInx];
			data[valueInx] = data[valueInx / 2];
			data[valueInx / 2] = temp;

			valueInx = valueInx / 2;
		}

	}
	
	void pop() {
		data[1] = data[len-1];
		data[len--] =0;
		
		int index=1;
		
		while(true) {
			int gotoIndex = -1;
			
			if(index*2 >= len) break;
			if((1<= index*2 && index*2 < len)&& (index*2+1) >= len){
				gotoIndex = index*2;
			}
			
			if(data[index*2] < data[index*2+1])
			{
				gotoIndex = index*2;
				
			}else {
				gotoIndex = index*2+1;
			}
				
			
			
			if(data[index] > data[gotoIndex]) {
				int temp = data[index];
				data[index] = data[gotoIndex];
				data[gotoIndex] = temp;
				
				index = gotoIndex;
			}else break;
			
		}
	}
	
	int top() {
		return data[1];
	}

}

 

@ 결론

트리는 직접 구현할 일이 거의 없다.

- 그래프의 구현을 배우면 트리 구현을 자연스럽게 습득

목적이 확실한 자료구조가 더 익히기 쉽다.

- 힙은 스택/큐/트리 처럼 심오한 의미가 있진 않다.

힙의 목적: 우선 순위가 큰 걸 빠르게 찾는 것

즉 - 목적을 아는데 좀 중요하다. 이걸 왜 만들었나 이런걸 아는 것이 자료구조에서 중요하다.

 

힙: 우선 순위

스택: 발자취 기억하기 위해서 

큐: 스케줄링, 병렬화

 

트리문제라도 트리를 구현할 필요가 없을 수 있다.

- 굳이 트리를 저장하지 않아도 되는 경우가 있다.