[자료구조 알고리즘] 기능성 이진트리 - 우선순위큐, 힙

[구현코드 - github]

- primitive val heap : https://goo.gl/FYP5im

- heap<T> : https://goo.gl/kc6KKT

[우선순위큐]

1) 입구 - 출구가 나뉘어져있어서 붙여진 이름 큐

2) 비선형자료구조 : 우선순위에 의해 계층적으로 데이터를 표현/동작, 선형자료구조인 큐와는 다름(단지 입출구때문에)

3) 우선순위에 의해서 Out 순서가 정해짐 : 들어온 순서는 상관없음

4) 힙을 기반으로 만들어짐 : 내부적으로 힙을 사용, 힙의 메서드 호출, 같은 구현내용

[힙 소개]

- 배열로 만들어지는 이진트리 : 삽입, 삭제 과정에서 트리의 마지막노드를 알아야 쉽게 구현할 수 있어서

- 기능성 이진트리 : 우선순위에 의한 내부 정렬 + 데이터 계층 표현

1) 조건 : 완전이진트리 + 부모노드 데이터 우선순위 높아야함

2) 동작

- 삽입 : (삽입후 정렬) - 우선 마지막노드에 넣어놓고 우선순위에 의한 정렬

- 삭제 : (삭제후 정렬) - 루트노드 삭제하고 우선 마지막노드를 루트노드로 가져놓은다음 우선순위에 의한 정렬

3) 알아둘 것

- 배열은 삽입,삭제과정을 편하게하려고 사용 : 연결리스트 기반 이진트리처럼 왼쪽 오른쪽 노드가 나눠져있지않음

(1) 인덱스로 나눠야하는데 부모 / 왼쪽, 오른쪽 인덱스 알 수 있는 공식만 알고있으면 됨

(2) 부모노드 인덱스 : 왼or오노드/2

(3) 왼쪽노드 인덱스 : 부모노드*2

(4) 오른쪽노드 인덱스 : (부모노드*2)+1

- 인덱스 시작은 1부터 하는게 좋음 : 0부터하면 또 생각해야할 것이 많아짐, 개수 == 마지막 저장된 인덱스

- 왼쪽 자식노드가 마지막노드(개수 == 인덱스)라면 왼쪽 자식노드만 있는 것

- 데이터의 우선순위는 만드는 사람이 정한다!

- 삽입 후 우선순위 비교할 때 같은 레벨은 신경안쓴다

[알아두기]

1) 힙은 우선순위큐다, 우선순위큐는 힙이다 모두 틀림
- 같은 특징이지만 엄연히 각각 존재