[자료구조] 우선순위 큐의 구현(2) - Helper

[자료구조] 우선순위 큐의 구현(2) - Helper Function

--> 초기화와 힙이 비었는지 확인하는 함수

--> 그리고 특정 노드의 인덱스를 전달하면, 부모 노드, 왼쪽 자식, 오른쪽 자식의 인덱스 값을 반환하는 함수

특정 노드의 부모, 왼쪽 자식, 오른쪽 자식 노드의 인덱스 값을 반환하는 함수의 구현이 이해가 되지 않는다면

우선순위 큐의 이해(3)으로 가서 인덱스 값을 구하는 간단한 공식을 이해해야 한다.

우선 순위가 높은 자식의 인덱스 값을 반환하는 함수

설명에 들어가기 앞서 힙은 완전 이진 트리라는 것을 다시 한번 숙지하자!

(1) 완전 이진 트리에서 왼쪽 자식 하나만 있는 트리는 0개 혹은 1개 뿐이다!

(2) 왼쪽 자식이 하나만 존재하는 트리가 있다면 그 왼쪽 자식 노드는 마지막 노드이다!

1. 자식 노드가 없는 경우

--> 왼쪽 자식 노드가 들어 갈( 혹은 들어간 ) 자리의 인덱스 값이 저장된 데이터의 개수보다 클 경우

--> 자식 노드가 존재하는 경우라면 총 데이터의 개수보다 클 수가 없다. (자식 노드 또한 데이터의 개수에 카운트 되었기 때문)

2. 자식 노드가 하나 있는 경우

--> 자식 노드가 하나 있는 경우는 완전 이진 트리에서 단 하나의 노드밖에 있을 수 없다.

--> 완전 이진 트리는 왼쪽부터 차곡차곡 저장되어 나가기 때문에 당연한 결과이다. (이해가 안된다면 그림을 그려보자.)

--> 또한 왼쪽 자식노드 하나만 존재하는 경우라면 그 노드는 힙에 저장된 마지막 노드이다.

--> 따라서 왼쪽 자식 노드의 인덱스와 저장된 데이터의 총 개수가 같다면 이는 자식 노드가 하나만 있는 경우이다.

3. 둘 다 존재하는 경우

--> 두 노드의 우선순위를 비교해서 우선순위가 높은 놈을 리턴한다.

--> 위에서 설명한 우선순위가 높은 노드를 리턴하는 방식은

매우 대표적인 연산문이기 때문에 잘 이해를 해 놓아야 한다!

오늘은 우선순위 큐를 구현하기 위한 Helper Function에 대해 알아보았다.

다음 포스팅부터는 삽입, 삭제에 대한 구현에 대해 다뤄보도록 하겠다.