힙은 루트에 가장 힙한 녀석을 두는 트리이다. (응?) 루트에 항상 최대 또는 최소값을 두기 때문에 최대 최소값을 빠르게 얻을 수 있다. O(1)
힙은 완전 이진트리의 모습을 띄는데, 부모 노드가 자식 노드보다 크거나(최대힙) 작은지(최소힙) 만을 보장한다. 즉, 같은 자식노드 끼리는 큰지 작은지를 비교할 수가 없다.
힙은 배열로 구현하면 공간, 시간 복잡도 측면에서 좋기 때문에 배열로 많이 구현한다.
배열로 구현했을 때 다음과 같이 인덱스를 구할 수 있다.
parent: (i-1) * 2
left: i/2 + 1
right: i/2 + 2
인덱스를 1부터 시작하면 parent: i*2, left: i/2 right: i/2+1 로 구할 수도 있다.
잘 보면 오른쪽 노드 = 왼쪽노드 + 1 이다. 옆에 차곡차곡 쌓이는 이진트리임을 다시 한번 확인할 수 있다. 따라서 마찬가지로 이진트리의 원리들이 적용된다.
힙의 높이는 floor(log2(n))
만약 노드가 가득 차 있고 층의 높이를 k 라고 한다면 (층: 0~k)
특정 층의 노드의 개수는 2^(k),
해당 층을 제외한 노드의 개수는 2^(k) - 1
모든 노드의 개수는 2^(k+1) - 1
삽입 삭제를 살펴보기 전에 근본이 되는 개념부터 알아보자.
힙은 모두 정렬되어 있는 것이 아니라 루트 노드만 최대/최소인지를 보장하면 되기 때문에 삽입/삭제 역시 문제가 되는 녀석과 부모 혹은 자식 노드와 비교해 제 자리를 찾아주기만 하면 된다. 따라서 시간 복잡도는 O(log n)이다.
제 자리를 찾아주는 방법은 두 가지가 있다.
shiftUp, shiftDown이라고 부르는데,