코딩테스트 - 패스트캠퍼스 챌린지 07일차

수강한 강의
Chapter 11 자료구조 (힙)
- 힙 구조
- 힙 구조 java 구현

학습 후기
꾸준히 한지 이제 1주일이 지났다 50일 환급 챌린지를 작성하면서 주말과 연휴 상관없이 50일 동안 계속 강의를 듣고 블로그에 글을 올린다는 생각에 너무한다(?)라는 생각하도 하지만 그래도 반 강제적으로 이렇게 하니 꾸준하게 강의를 듣고 있어 작심삼일(?)형의 마인드인 나에게 조금 좋은거 같기도 하다.
힙을 java의 ArrayList를 사용하여 구현해 보았다. 힙은 최대값 최솟값을 빠르게 찾기 위한 완전 이진 트리이다. Max Heap은 최상단 노드에 최댓값이 들어있고 Min Heap에서는 최상단 노드에 최솟값이 들어있다. 완전 이진 트리란 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리로 트리를 구현할 때 사용한 이진 탐색트리와 비교해 보자면 공통점은 둘다 이진트리라는 점이고 차이점은 Max Heap에서의 완전 이진 트리는 각각의 노드는 자식노드보다 크거나 같지만(자식노드 < 부모노드), 이진 탐색 트리는 자신의 노드값을 기준으로 왼쪽 자식 노드값은 작고 오른쪽 자식 노드값은 크다.(왼쪽 자식노드 < 부모노드 < 오른쪽 자식노드) 그래서 이진 탐색 트리는 탐색을 위한 자료구조이고 힙은 최댓값, 최솟값을 검색하기 위한 자료구조로 기억하면 된다. 힙 클래스에 노드를 삽입하는 insertNode 메소드와 노드를 삭제하는 deleteNode를 구현하였다. insertNode 메소드에서는 힙의 특징으로 새로운 노드를 삽입할 때 최하단 왼쪽 노드부터 삽입하기에 ArrayList로 구현되어 있어 List에 그냥 add로 간단하게 추가하고 이제 추가된 값을 기존 노드들과 크기를 비교하여 최상단 노드까지 올리기 위해 swap 메소드를 사용하여 구현하였다. deleteNode 메소드는 힙에서 보통 중간에 있는 노드값이 아닌 최상단 노드값을 제거하게 되는데 제거후 자식 노드들의 크기를 비교하고 다시 최상단노드부터 채워 넣기 위해 여기서도 swap 메소드를 사용하여 구현하게 된다. 힙에서의 시간 복잡도는 삽입, 삭제시 O(log n)이다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.