문돌이 존버/프로그래밍 스터디
2021. 7. 18.
자료구조 힙(heap) 알아보기
본 글은 여러 블로거님들의 훌륭한 지식을 참고하여 작성하였습니다. 감사드립니다. 힙(Heap) 오늘은 자료구조 중 힙에 대해 스스로 정리하고 다시 이해해보려고 한다. 힙의 세 가지 큰 특징(Max heap 기준) 1. 루트 노드가 항상 최댓값을 지님 -> 이를 Heap propoerty라 함 2. 반드시 완전 이진 트리(complete binary tree)여야 함 3. 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙 참고로 포화 이진 트리(perfect binary tree)와 완전 이진 트리는 아래 그림과 같다. 포화 이진 트리: 루트로부터 시작해서 맨 마지막 레벨까지 모든 노드가 정확히 2개씩의 자식 노드를 가지도록 꽉 채워진 트리(노드 수가 $2^k - 1$일 때만 가능) 완전 이..
