힙 (Heap)

힙은 부모의 값이 항상 자식보다 우선순위가 높은 (사진상에서는 작은 숫자가 우선순위가 높다고 가정) 완전 이진 트리이다.

완전 이진 트리는 자식이 항상 2개이고, 왼쪽에서 오른쪽방향으로 원소가 추가 되는 트리를 말한다.

힙에서는 2가지 연산을 할 수 있다.

1) 원소를 추가하는 연산

2) 원소를 삭제하는 연산

힙에 값을 삽입할 때 힙은 완전 이진 트리이기 때문에 무조건 사진의 화살표 방향으로 원소를 추가해야 한다.

위의 사진상에 4를 추가한다고 해보자.

4를 추가하면 사진처럼 완전이진트리에 삽입된다.

근데 힙은 항상 부모 노드의 값이 자식노드보다 우선순위가 크기 때문에 4를 삽입했을 때 올바른 자리가 아니다.

그러기 때문에 4노드의 부모노드인 7과 우선순위를 비교해서 자리를 바꿔줘야 한다.

4와 7의 자리를 바꾼다.

이제 4의 부모노드인 3과 우선순위를 비교해야 하는데, 3이 우선순위가 더 높기 때문에

4의 올바른 자리는 저곳이 된다.

이제 27을 삽입해보자. 완전이진트리이기 때문에 사진상의 자리에 27이 삽입된다.

그리고 부모인 23과 비교해보면 27이 우선순위가 더 낮기 때문에 그대로 있는다.

다음으로 2를 힙에 삽입한다.

그럼 23과 우선순위를 비교해서 자리를 바꾸게 된다.

5와 우선순위를 비교해서 자리를 바꾸게 된다.

3과 우선순위를 비교해서 자리를 바꾸게 된다.

2는 가장 마지막 자리에 삽입 했지만, 힙에서 우선순위가 가장 높은 숫자이기 때문에 

가장 우선순위가 높은 노드까지 올라 가게 된다.

결론은 삽입연산을 했을 때 삽입한 원소의 부모노드와 우선순위를 검사해서 올라간다는 점이다.

여기에서 완전이진트리의 높이에 대해서 생각 해 봐야한다.

---

사진에서 처럼 노드의 개수가 1일 때 완전이진트리의 높이는 1이다.

노드의 개수가 3일 때 완전이진트르의 높이는 2이다.

노드의 개수가 7일 때 완전이진트르의 높이는 3이다.

노드의 개수가 15일 때 완전이진트르의 높이는 4이다.

여기에서 완전 이진 트리의 높이에 대한 규칙을 볼 수 있다.

사진에서처럼 노드의 개수가 

이면 높이가 1

이면 높이가 2

이면 높이가 3

각 2의 지수가 트리의 높이임을 확인 할 수 있다.

즉, 노드가 n개 일 때 높이는 log n 이다.

또, 높이가 1에서 2가 되면 노드의 개수는 1개에서 2개가 되고,

높이가 2에서 3이되면, 높이가 2에서 4가 되는 것을 볼 수 있다. 

(높이가 2이면 노드의 개수가 3일 수 도 있는데, 노드의 개수가 6개이면 높이도 3이기 때문에 마찬가지이다.)

그래서 높이가 1이 증가하면 노드의개수는 2배가 되는 규칙을 발견할 수 있다.

완전 이진 트리에서의 노드의 개수n에 따른 높이가 log n 인 것을 확인하였기 때문에,

힙에서 삽입연산시 시간복잡도를 구해볼 수 있다.

사진에서 처럼 힙에 1을 삽입하였다고 가정해보자.

1을 삽입하면 가장 우선순위가 높기 때문에 제일 높은 노드에 1이 위치하게 된다.

즉 값을 삽입하면 최악의 경우 O(log n)이 걸리므로

힙에서 삽입의 시간복잡도는 O(log n)이다.

---

이제 힙에서의 삭제연산에 대해 알아보자. 힙에서 삭제를 하면 제일 우선순위가 높은 루트노드의 값을 먼저 삭제한다.

삭제하게 되면 위의 그림처럼 되는데, 루트노드의 자리가 비어있기 때문에, 힙에서 가장 마지막 값 23을 루트노드에 가져온다.

23을 루트노드에 가져오면 위의 상태가 되는데, 23은 저 자리에 어울리지 않는다. 

왜냐하면 제일 높은 우선순위의 숫자가 위치 하여야 되기 때문이다.

그래서 23의 자식인 3과 4중에서 우선순위가 높은 숫자와 비교를 해서 자리를 바꿔 주어야 한다.

4보다는 3이 우선순위가 높기 때문에 3과 23을 비교해서 자리를 바꿔준다.

하지만 23의 자리역시 맞는 자리가 아니다. 왜냐하면 23의 자식인 5와 7이 23보다 우선순위가 높기 때문이다.

그래서 5와 7을 비교해서 우선순위가 높은 숫자와 23을 바꿔준다.

5가 7보다 우선순위가 높기 때문에 5와 23의 자리를 바꾼다.

그리고 나서 보니까 23의 자식은 이제 27 밖에 없는데 23은 27보다 우선순위가 높다.

그러므로 한번의 힙에서의 삭제연산이 끝나게 된다.

힙에서 삭제의 시간복잡도를 보면 최악의 경우 힙의 마지막에 있던 수가 

가장 위로 올라가서 똑같이 가장 밑으로 내려오는 것이다.

그러므로 삭제연산에서 삽입과 마찬가지로 시간복잡도는 O(log n) 이다.

출처 : AlgorithmLABS