힙(우선순위 큐) 구현 #1

힙 구현은 곧 우선순위 큐의 완성으로 이어진다.

 

일반적으로 큐는 FIFO 이다. 

 

하지만 우선순위 큐의 OUT은 들어간 순서 상관 없이 우선순위에 따라 나온다.

 

 

힙(Heap)이란?

 

1. 힙은 '이진트리' 이되 '완전 이진트리'이다

 

2. 모든 노드에 저장된 값은 자식 노드에 저장된 값도가 크거나 같아야한다.

 

3. 같은 노드 사이는 상관 없다.

 

 

힙은 최대 힙(Max Heap) 과 최소 힙(Min Heap)이 있는데 

 

루트노드로 올라갈수록 저장된 값이 작아지면 최소 힙, 커지면 최대 힙이라고 한다.

 

Min Heap

 

 

힙에서 데이터 저장 과정

 

위 그림처럼 힙이 있다고 하자

 

 

여기에 9라는 데이터를 저장한다고 하면 일단 완전 이진트리를 만든다.

 

 

부모노드와 우선순위를 비교해서 높으면 부모노드와 바꿔 준다. 부모노드가 우선순위 클때까지

 

9는 1보다 우선순위가 작으므로 더이상 Switching은 일어나지 않는다.

 

 

 

힙에서 데이터 삭제 과정

 

위 노드에서 1을 삭제해보자

 

1을 삭제 한 후 마지막 노드를 삭제한 노드로 옮긴다.

 

 

자식노드 중 우선순위가 낮은 노드와 비교해서 우선순위가 낮으면 자식노드와 교체한다.

 

 

40하고 80을 비교해보면 80이 오히러 우선순위가 낮기 때문에 교체하지 않는다.

 

 

 

이제 실제 위 최소힙을 구현해보자

 

요구 사항

1. 힙은 배열로 구성한다.

2. 힙의 첫번째 인덱스는 비워둔다 (편의상)

3. 데이터는 항상 왼쪽에서 오른쪽으로 채운다.

4. 한노드당 자식노드는 최대 2개이다.(Left, Right)

5. 우선순위가 클수록 부모노드로 올라간다.

6. 숫자가 작을수록 우선순위가 높다.(Min Heap)

 

저장기능 설계

1. 저장할 데이터를 마지막 노드에 추가한다.

2. 부모노드와 우선순위를 비교한다.

3. 부모노드보다 우선순위가 크면 교체한다. (아닐 때 까지)

 

삭제기능 설계

1. 데이터 삭제 후 마지막 노드의 데이터를 삭제된 노드로 옮긴다.

2. 자식노드들과 우선순위를 비교한다. (삭제된 노드에서)

3. 자식노드보다 우선순위가 작으면 교체한다.