[Java] Heap, 힙 , 트리, 이진트리, 완전 이진트리

Heap(힙)

힙은 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조이다.

힙을 알기전에 트리구조 부터 알아보자.

 

Heap(힙)은 우선순위큐 구현에 사용된다.

 

트리구조란?

위와 같은 구조가 트리구조이다. 

부모 노드(parent node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 높은 노드를 의미 (ex. F의 부모노드 : B)

자식 노드(child node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 낮은 노드를 의미 (ex. C의 자식노드 : G, H)

루트 노드 (root node) : 일명 뿌리 노드라고 하며 루트 노드는 하나의 트리에선 하나밖에 존재하지 않고, 부모노드가 없다. 위 이미지에선 녹색이 뿌리노드다.

단말 노드(leaf node) : 리프 노드라고도 불리며 자식 노드가 없는 노드를 의미한다. 위 이미지에서 주황색 노드가 단말노드다.

내부 노드(internal node) : 단말 노드가 아닌 노드

형제 노드(sibling node) : 부모가 같은 노드를 말한다. (ex. D, E, F는 모두 부모노드가 B이므로 D, E, F는 형제노드다.)

깊이(depth) : 특정 노드에 도달하기 위해 거쳐가야 하는 '간선의 개수'를 의미 (ex. F의 깊이 : A→B→F 이므로 깊이는 2가 됨)

레벨(level) : 특정 깊이에 있는 노드들의 집합을 말하며, 구현하는 사람에 따라 0 또는 1부터 시작한다. (ex. D, E, F, G, H)

차수(degree) : 특정 노드가 하위(자식) 노드와 연결 된 개수 (ex. B의 차수 = 3 {D, E, F} )

 

 

이진트리란?

위 트리구조에서 특정한 형태로 제한을 한 트리로서

모든 노드의 최대 차수를 2로 제한한것이다. -> 각 노드는 자식노드를 최대 2개까지밖에 못가진다.

 == 이진트리(Binary Tree)

 

 

완전 이진트리란? ( Complete Binary Tree)

완전 이진트리란 마지막레벨을 제외한 모든 노드가 채워져있으면서 모든 노드(==사실상 마지막 레벨의 노드들)이 왼쪽부터 채워져 있어야한다.

 

즉 완전 이진트리는 이진트리에서 두가지 조건을 더 만족해야한다.

1. 마지막 레벨을 제외한 모든 노드가 채워져있어야한다.

2. 모든노드들은 왼쪽부터 채워져 있어야한다.

 

완전 이진 트리에서 한 가지 조건만 더 추가하면 '포화 이진 트리(perfect binary tree)'가 된다. 바로 '마지막 레벨을 제외한 모든 노드는 두 개의 자식노드를 갖는다'라는 조건이다. 

즉 완전 이진트리는 노드를 채워나가는데(노드가 추가될때) 왼쪽 -> 오른쪽 방향으로 노드를 추가해나가야한다.

그리고 다음레벨을 가기전에 해당 레벨에 노드는 가득 채워야한다(이진트리니까 2개씩)

 

 

 

 

다시 힙으로

힙은 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조이다.

라고 했다.

 

힙은 어떻게 구현될까?

완전 이진트리를 이용하여 최솟값 또는 최댓값을 빠르게 찾아내려면 

어떤식으로 완전 이진트리가 구성되어있어야할까?

 

예를들어)

숫자가 낮을수록 우선순위가 높다고 했을때

어떤 리스트에 값을 넣었다 빼면서 우선순위가 높은것부터 빼내려고 하면 대개 정렬후 첫번째 인덱스를 뽑아낼것이다.

새로운 숫자가 들어올때마다 정렬을 하면 비효율적이라. 

 

다음과 같은 조건을 붙였다.

 

"부모 노드는 항상 자식노드보다 우선순위가 높다."

 

즉 부모노드는 자식노드보다 항상 우선순위가 앞선다는 조건만 만족시키며 완전 이진트리형태로 채워나가는것이다.

 

   [부모 노드(parent node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 높은 노드를 의미] 

부모노드가 항상 자식노드보다 우선순위가 높다는것은 

 

루트노드는 모든 노드들보다 우선순위가 높다는뜻이 된다. 

 

이러한 원리로 최댓값 또는 최솟값은 루트노드를 가져오면 되니까 O(1)의 시간복잡도를 가지고, 

 

삽입 삭제 연산시에도 부모노드가 자식노드보다 우선순위만 높으면 됨을 이용하여 노드를 정리해주면 되서 O(logN)의 시간복잡도를 가져 빠르게 수행 가능하다.

 

위 이미지에서도 볼 수 있지만

부모노드와 자식노드간의 관계만 신경쓰면 되기 때문에 형제 간 우선순위는 고려되지 않는다.

이러한 정렬 상태를 흔히 '반 정렬 상태' 혹은 '느슨한 정렬 상태' , '약한 힙(weak heap)'이라고도 불린다.

 

"왜 형제간의 대소비교가 필요 없다는 거죠?"

 

우선순위가 높은 순서대로 뽑는 것이 포인트다.

 

즉, 원소를 넣을 때도 우선순위가 높은 순서대로 나올 수 있도록 유지가 되야하고

 

뽑을 때 또한 우선순위가 높은 순서 차례대로 나오기만 하면 된다.

 

최소 힙 : 부모 노드의 값(key 값) ≤ 자식 노드의 값(key 값)

최대 힙 : 부모 노드의 값(key 값) ≥ 자식 노드의 값(key 값)

 

 

 

 

 

 

 

출처,더 자세한정보

https://st-lab.tistory.com/205

자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기

https://hongjw1938.tistory.com/18

자료구조 - 트리(Tree), 이진 트리(Binary Tree)