[2019 동계 모각코] 5차시 - 결과

완전이진트리와 히프 알고리즘

 

---

1. 완전이진트리 이해

완전이진트리란 이진트리에서 리프가 왼쪽부터 순서대로 채워지는 것이다.

부모의 인덱스가 i 라면 자식의 인덱스는 2i+1, 2i+2가 된다.

​

2. 히프 알고리즘

완전이진트리에서 리프-루트로 가는 경로가 오름차순 또는 내림차순으로 되어있는 것이다.

맥스히프 : 오름차순으로 되어있는 완전이진트리

히프화 : 히프 특성을 만족하도록 원소들을 재배열

​

1) 히프화메소드 - Max_heapify()

: 부모와 자식간의 크기를 비교하여 원소를 배열하고 재귀를 통해 부모에서 리프까지 재배열한다.

 

​

2) 삽입메소드 - push(), pushSort()

: 트리의 맨마지막에 삽입하고 부모와 비교하며 리프-루트경로로 원소를 재배열한다.

 

push(int x) - 크리를 하나 늘린 배열을 생성하고 원래 배열에서 값을 옴긴뒤 마지막에 삽입한다. 이후 배열의 이름을 원래 배열 이름으로 바꿔준다. 부모의 인덱스를 매개변수로하여 히프화 메소드를 실행한다.

pushSort(int i) - 부모의 위치에서 히프화메소드를 실행하고 리프-루트 경로를 위해 부모의 부모 인덱스를 매개변수로 하여 재귀한다.

​

3) 삭제메소드 - pop()

: 루트의 값을 삭제하고 트리의 가장 마지막 값을 루트로 옴긴뒤 히프화한다.

값을 옴긴뒤 배열의 크기를 줄이고 히프화메소드를 실행한다.

​

4) 히프 구축 메소드 - Build_Max_Heap()

: 주어진 배열의 리프-루트경로로 리프가 아닌곳부터 히프화한다.

​

5) 생성자, swap, 출력 메소드

 

​

6) 메인메소드 & 결과

 

---

느낀점

완전이진트리의 개념은 생각보다 간단했고 히프 알고리즘이 어려워서 이해하는데 오래걸렸다. 모각코 시간내내 질문하면서 히프화, 삽입, 삭제, 히프 구축 메소드를 이해하고 코드를 작성했다. 재귀가 들어가있다보니 생각하는게 더 어려워져서 그림을 그리거나 디버깅을 해보면서 메소드를 작성했다. 이해하고 나서는 트리구조나 히프알고리즘에 재미를 느꼈고 다른 트리구조를 공부할 때도 흥미를 가지고 할 수 있을것 같다.