without haste but without rest

힙(Heap) 힙은 최대값과 최소값을 빠르게 찾기 위한 이진 트리다. 이진 탐색 트리(Binary Serach Tree)처럼 동일한 이진 트리라는 공통점이 있다. 하지만 트리와 힙은 다르다. 가장 큰 차이점은 힙의 경우 최대값이나 최소값이 루트 노드에 자리잡고 있다는 것이다. 또한 이진 탐색 트리의 경우 링크드 리스트 구조로 각 노드를 연결하는 반면 힙은 배열을 이용한다. 위 이미지의 구조가 트리였다면 level 2에 위치하는 3과 1은 왼쪽 노드에 존재해야한다. 하지만 힙은 삽입 데이터의 크기에 따라서 좌우 정렬을 하지 않는다. 목적 자체가 최소, 최대값을 빠르게 찾기 위함이기 때문에 최대값, 최소값을 루트 노드에 위치 시키는 것이 가장 중요하다. (위 이미지의 경우 최대 힙이므로 자식 노드는 부모 노..