[자료구조] 우선순위 큐의 구현(1) - 배열 기반 힙(heap)

[자료구조] 우선순위 큐의 구현(1) - 배열을 기반으로 한 힙의 구현

힙은 배열을 기반으로 구현하는 대표적인 이진트리이다.

-> 연결 리스트 기반은 마지막 위치에 새로운 트리를 추가하는 것이 쉽지 않다.

-> 배열을 기반으로 구현하는 이유는 힙의 마지막 위치에 추가하는 것이 쉽기 때문이다.

(우선순위 큐를 위한) 힙의 구현

1. 구현의 편의를 위해 배열의 인덱스 0은 비워둔다.

2. 왼쪽 자식의 노드의 인덱스 값 --> 부모 노드의 인덱스 값 x2

3. 오른쪽 자식의 노드의 인덱스 값 --> 부모 노드의 인덱스 값 x2 +1

4. 부모 노드의 인덱스 값 --> 자식 노드의 인덱스 값 /2 --> 정수형 나눗셈

꼭 알아야 할 점

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

2. 배열 기반 (인덱스 0은 비워두기)

3. 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다.

4. 노드의 고유 번호가 저장되는 배열의 인덱스 값이 된다.

5. 우선순위를 나타내는 정수값이 적을수록 높은 우선순위를 나타낸다고 가정!

--> 힙에 저장된 노드의 개수와 마지막 노드의 고유 번호가 일치하기 때문에

마지막 노드의 인덱스 값을 쉽게 얻을 수 있다. 

(우선순위 큐를 위한) 힙의 헤더파일

오늘은 우선순위 큐의 구현을 위한 (우선순위 큐에 치우쳐진) 힙 구현에 대해 간단하게 알아보았다.

계속 해서 우선순위 큐의 구현에 대해 다룰 것이며, 위의 헤더파일에 다뤄진 함수들을 차근차근 구현해 나가도록 하겠다.