우선순위 큐와 힙(heap) (2) 힙의 정의

힙은 완전이진트리 구조로 느슨한 정렬상태를 가지고 있다.

 

부모노드의 키값이 자식노드의 키값보다 항상 크다. 부모가 같은 자식 노드끼리는 그 값의 크고 작음은 상관이 없다.

그래서 느슨한 정렬이라고 부르는 것이다.

 

이 구조로 구현하면 새로운 노드를 삽입하는 과정이나 가장 키값이 큰(=우선순위가 가장큰)노드를 삭제하고 재정렬하는데 복잡도가 O(log_2_n)으로 줄어든다. 가령 이미지 처럼 3(n=10)의 값이 들어온경우 3은 그 부모노드의 우선순위 값인 4와 7, 그리고 9까지 총 세 번만 비교를 하면 된다. (log_2_10=3.x)으로 복잡도가 3이 된다.

모든 노드와 비교 할 필요 없는 것이 힙의 장점이다.

 

삽입하는 경우는 위에서 설명했고 삭제하는 경우는 맨마지막 노드 (last)를 맨처음 노드 root에 올리고 재정렬하는 방식이다.

3이 root자리(맨 위자리)로 가고 7과 비교해서 내려오고, 5와 비교해서 내려오고, 2와 비교해서 크므로 더 이상 이동하지 않고 거기서 종료한다. 삭제 연산 또한 O(log_2_n)의 복잡도를 가지게 된다.

 

 

힙을 구현할 때 노드의 number를 계산하기 쉽게 배열을 이용한다.

다음과 같이 작성함. index 0은 비워둔다. 왜? 자식의 노드, 부모의 노드 값 계산이 쉽게 하기 위해서 이다. 1부터 시작하면 자식의 노드는 부모의 노드index*2, 노드index*2+1의 값을 가지게 된다. 따라서 노드의 number를 계산하는 과정이 간단해진다.

 

코드로 힙을 나타내고 삽입, 삭제 연산까지 시행해보자.

먼저 구현. 전체 코드는 다음과 같다.

 

코드를 세부적으로 설명하면

(10)에 있는 heap_size변수는 현재 힙에 들어가 있는 노드의 수를 나타낸다. 가령 비어있으면 0, 하나 들어와있으면 1, 10개 들어가 있으면 10의 값을 가진다.

힙의 사이즈를 200으로 선언했으므로 배열은 0~199의 인덱스를 가지게 되고

0번은 비워둔다고 했으므로 노드는 최대 199개가 들어갈 수 있다. 17, 18을 보면 해당 개념에 대한 코딩을 확인할 수 있다. heap_size == 199이면 full_heap함수가 1을 리턴하고 heap_size == 0이면 empty_heap 함수가 1을 리턴한다.

 

(11~13)에 있는 코드는 아까 말했던 자식, 부모 노드의 계산을 코드로 나타낸 것이다. 가령 index=i인 노드의 부모노드의 index를 찾으려고 한다면 i/2값이 그 부모노드의 index가 될 것이다. i는 int형이므로 2.5, 3.5의 값이 나온다면 2, 3으로 받기 때문에 index가 홀수일 때도 해당 코드는 문제가 없다.

 

다음 글에서 삽입, 삭제 연산의 코드를 설명하겠다.