[알고리즘] 09. 힙 자료구조
내용 정리
오늘은 binary heap에 대해 배웠다.
min-heap과 max-heap으로 나누어지는데 서로 반대이기 때문에 거의 min-heap으로 배웠다.
binary tree의 일종인 binary heap은 top, pop, push 세가지 연산이 가능하다.
pop과 push는 직관적인데 top은 min-heap의 경우 가장 작은 값을 찾는 경우다.
이때 top값은 항상 root node에 위치하기 때문에 항상 theta(1)의 복잡도를 가진다.
이후 perfect binary tree와 complete binary tree에 대해서 배우고 특히 complete binary tree의 세가지 연산을 다시 알아보았다.
perfect binary tree는 전체 node개수가 항상 (2^n-1)개라서 연산의 제약을 받는다.
complete binary tree의 push연산을 배우면서 평균 push연산의 complexity를 구해보았는데
그 논리와 수학적 증명이 너무너무 재밌었다!!
그리고 그 결과가 결국 theta(1)이 된다는 점도 놀랍고 흥미롭다.
더 복잡할 것이라고 생각했는데..
binary tree는 구현 시 array로 구현한다.
BFS순서대로 arrary를 채우기에 index에 2를 곱하면 왼쪽 자식 node가 나온다는 점을 이용하여 코드를 효율적으로 작성할 수 있다.
9주차 수강 후기
9주차 필기를 하고 블로그에 정리하는 건 좀 미뤘더니 기억이 그새 잘 안난다.
역시 바로바로 기록하는 것이 중요하다.
간만에 수식적 내용을 배웠더니 정말 재미있었다.
코드 실습보다 저런 증명이 더 재밌을 것 같은데, 코드 실습 위주 강의라 조금은 아쉬웠다.
그래도 허재필 교수님께서 쉽게 알려주셔서 편안하다.