궁금한게 많은 개발자 노트

시험장에서 자주 사용하는 Heap에 대해 적어보려한다. Heap이란, 최솟값이나 최댓값을 빠르게 찾아 내기 위해 고안된 완전이진트리의 일종으로 우선순위큐라고도 불린다. (적다보니 트리에 대해서도 적어봐야지 싶다) Heap에는 최대힙(Max Heap), 최소힙(Min Heap)이 있는데 부모 자식노드 관계에 따라 정해진다. 예를들어, A가 B의 부모 노드라면, A의 key값과 B의 key값은 대소관계가 성립한다 (Max는 부모가 key값이 크다) -> key(T.parent(v)) key(v) 일반적으로 정렬을 해야할 상황이 생기면 Heap에 모두 넣고, 하나씩 빼면 정렬된 형태로 값을 얻을 수 있어서 자주 사용하며 시간복잡도는 O(logN)으로 Qu..