패스트캠퍼스 챌린지 13일차
[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.
힙이란 무엇일까?
힙은 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조이다. 완전 이진 트리(Complete Binary Tree)로 노드를 삽입할 때 좌측 최하단의 노드에서부터 차례대로 삽입한다.
힙을 사용하는 이유는 시간 복잡도 때문이다. 기존의 배열에서는 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(n)이 소요되지만, 힙의 경우에는 O(log n)이 소요되므로 효율성이 좋다. 우선순위 큐처럼 최댓값 또는 최솟값을 빠르게 찾기 위한 자료구조 및 알고리즘 구현에 활용되어진다.
힙의 구조
힙은 최댓값을 구하기 위한 구조(Max Heap)와 최솟값을 구하기 위한 구조(Min Heap)로 분류할 수 있다. 그리고 다음의 조건에 따라 자료구조가 생성된다.
자료구조 생성 조건
1. Max Heap의 경우, 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다.
반대로, Min Heap의 경우 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작다.
2. 완전 이진트리 형태를 가진다.
이진 탐색 트리의 공통점과 차이점
공통점으로는 힙과 이진 탐색 트리는 모두 이진 트리이다. 차이점으로는 Max Heap 기준, 힙의 경우 각 노드의 값이 자식 노드보다 크거나 같지만 이진 탐색 트리는 왼쪽 자식 노드의 값은 작고, 오른쪽 자식 노드의 값은 크다. 그리고 힙은 이진 탐색 트리와 다르게 자식 노드에서 왼쪽, 오른쪽에 대한 값의 기준이 없이 들어오는 순서대로 왼쪽부터 자식 노드로 구성된다.
패스트캠퍼스 [직장인 실무교육]
fastcampus.co.kr
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.