[자료구조] Heap

Heap

Heap의 정의

• complete binary tree
  
  • 마지막 level을 제외한 모든 level은 완전하게 꽉 차 있다.
  • 마지막 level은 왼쪽부터 채워진다.
• 부모의 key는 자식의 key보다 항상 우선순위가 높다.
  • 클수록 우선순위 높다면, 부모의 key는 자식의 key보다 항상 크다. (max Heap)
  • 작을수록 우선순위가 높다면, 부모의 key는 자식의 key보다 항상 작다. (min Heap)
• 왼쪽 child와 오른쪽 child 사이 순서는 존재하지 않는다.

Heap에서 보장되는 것

• 1. root가 우선순위가 가장 높다
  • 클수록 우선순위 높다면, root의 값이 가장 크다. (max Heap)
  • 작을수록 우선순위 높다면, root의 값이 가장 작다. (min Heap)
• 2. 어떠한 방향으로 내려가든, 내려갈수록 우선순위는 낮아진다.
  • 클수록 우선순위 높다면, 내려갈수록 값이 작아진다. (max Heap)
  • 작을수록 우선순위 높다면, 내려갈수록 값이 커진다. (min Heap)

 

값이 작을수록 우선순위가 높다고 가정했을 때(=min Heap), root에는 어떠한 값이 와야하는가?

 

Heap의 정의에 따르면, 부모노드는 자식노드보다 항상 우선순위가 높아야 하므로 1이 올 수 밖에 없다.

그렇다면 root의 child node에는 어떠한 값이 올 수 있는가?

 

2은 root 노드의 left child node가 될수도, right child node가 될수도 있다. 하지만 3-level에 위치할수는 없다.

• left, right 둘 다 올 수 있는 이유는 left와 right 사이 순서가 존재하지 않기 때문이다. (Heap의 정의)

2-level에 2보다 큰 값들이 오게 된다면,

자식 노드의 우선순위는 부모 노드의 우선순위보다 높을 수 없다는 정의 때문에 2가 어느 자리에도 들어갈 수 없다.

따라서 2은 반드시 2-level에 위치해야 한다.

 

여러가지 Heap이 완성될 수 있지만, 그 중 하나의 Heap이 될 수 있는 예시이다.

 

 

 

Heap의 구현

index	0	1	2	3	4	5	...	N
item	?	?	?	?	?	?		?

 

• heap을 만들 때는 배열을 주로 사용한다.
• 규칙
  • root는 배열 index 1에 위치한다.
  • index i에 위치한 Node의 child는 2*i(left child), 2*i+1(right child)에 위치한다.
    • index1의 자식 노드 -> index 2, index 3에 위치
    • index2의 자식 노드 -> index 4, index 5에 위치
    • index3의 자식 노드 -> index 6, index 7에 위치 
    • ...
    • 이런 식으로 배열을 순서대로 채워가며 자식 노드가 생성된다 (complete binary tree)
    • * 일반적으로 tree를 구현할 때 부모 노드와 자식 노드를 포인터로 연결해주는 것에 비해,
      heap은 배열의 index를 통해 부모 노드, 자식 노드로 이동할 수 있어 이동 속도가 더 빠르다.

 

 

Heap Insert = Up Heap

• 파란색 영역이 기존에 있던 Heap
• 어떤 노드를 추가하기 위해서는 어떠한 절차를 거쳐야 하는가?
  • 1. 초록색 위치에 노드를 추가한다. (배열의 가장 마지막에 원소를 추가한다)
  • 2. 추가한 노드의 위치를 f라고 한다면, f 노드와 c 노드 사이의 관계를 확인한다.
    • c 노드보다 f 노드의 우선순위가 낮다면 stop (heap의 정의에 부합하므로)
    • c노드보다 f 노드의 우선순위가 높다면 c노드와 f 노드 바꾸기 (heap의 정의에서 어긋나므로) 
      • f 노드와 a 노드 사이의 관계 확인
        • a 노드보다 f 노드의 우선순위가 낮다면 stop
        • a 노드보다 f 노드의 우선순위가 높다면 a 노드와 f 노드 바꾸기
          • 재귀적으로 수행 ...
• Heap의 정의에 부합할 때까지 root 쪽으로 올라가면서 swap을 진행 = Up Heap
• Up Heap은 O(logN) 정도가 소요된다.

 

 

Heap Delete = Down Heap

Heap에서 delete한다는 것은 우선순위가 가장 높은 root node를 삭제한다는 뜻이다.

root node를 삭제하면 다음과 같이 변한다.

 

그 다음에는 가장 마지막에 추가된 node를 root로 올린다.

 

 

 

그 다음 Heap의 정의를 충족하는지 검사한다.

• z가 b보다 우선순위 높고 AND c보다 우선순위 높다 (그럴일은 없지만)
  
  • stop
• z가 b보다 우선순위 높지 않거나 OR c보다 우선순위 높지 않다
  • b, c 중 우선순위가 높은 것과 z를 swap한다.
  • 이제는 z, d, e 사이의 관계를 체크한다.
    • z가 d보다 우선순위 높고 AND e보다 우선순위 높다
      • stop
    • z가 d보다 우선순위 높지 않거나 OR e보다 우선순위 높지 않다
      • d, e 중 우선순위 높은 것과 z를 swap한다.
      • 조건 만족할 때가지 이 과정 반복
• Heap의 정의에 부합할 때까지 leaf로 내려가면서 swap 진행 = Down-Heap
• Down Heap은 O(logN) 소요된다.

 

 

 

Up Heap & Down Heap 예제

이 상황에서 3.5 값을 지닌 node를 추가해보겠다. 우선 가장 마지막 위치에 추가한다.

 

 

 

3.5와 9를 비교한다. 현재 우선순위가 맞지 않으므로 두 노드를 swap한다.

 

 

이후 3.5와 4 노드를 비교한다. 역시 우선순위가 맞지 않으므로 두 노드를 swap한다.

그 다음 3.5와 1 노드를 비교한다. 우선순위가 맞으므로 stop한다.

Heap에서 노드 추가 완료

 

 

 

이번에는 node를 삭제해보겠다. Heap에서의 삭제는 우선순위가 가장 높은 노드를 삭제하는 것이다.

아래 Heap에서 1을 삭제한다. 그리고 가장 마지막에 추가된 node를 root로 올린다.

 

 

그 다음 9노드와 3.5, 2 사이의 관계를 파악한다.

3.5, 2보다 우선순위가 낮음에도 불구하고 root에 있으므로 swap이 필요하다.

3.5와 2 중 우선순위가 높은 것은 2이므로 2와 9를 swap한다.

 

그 다음 9 노드와 3, 5 노드 사이의 관계를 파악한다.

9노드는 3노드보다도 우선순위가 낮고, 5 노드보다도 우선순위가 낮으므로 swap이 필요하다.

3과 5 중 3의 우선순위가 높으므로 3 노드와 9 노드를 swap한다.

 

이제 Heap의 정의를 만족한다. delete 끝 !