[파이썬 알고리즘] 힙이란???

힙이란?

- 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

 

힙을 쓰면 좋은 이유

- 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조입니다.

- 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 간다.

- 따라서 최대의 값들을 빠르게 구할 수 있게 된다.

 

      8      Level 0
    6   3    Level 1
     2 1     Level 2  # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!

      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 1     Level 2  # 자식 노드보다 크니까 힙이 맞습니다!


      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 5     Level 2  # 자식 노드보다 크지 않아서 힙이 아닙니다..!

 

- 참고로, 힙은 다음과 같이 최대값을 맨 위로 올릴수도 있고, 최솟값을 맨 위로 올릴 수도 있습니다.

- 최댓값이 맨 위인 힙을 Max 힙, 최솟값이 맨 위인 힙을 Min 힙이라고 합니다!

- BST(이진탐색트리)와 다르다. 좌, 우 자식의 위치가 대소관계를 반영하지 않음.

- 계산 편위를 위해 인덱스는 1부터 사용한다.(parent: x, left: 2x, right: 2x+1)

 

최대 힙 - 삽입 알고리즘

힙의 규칙

- 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 합니다.

- 따라서, 원소를 추가하거나 삭제할때도 위의 규칙이 지켜져야 합니다.

1. 원소를 맨 마지막에 넣는다.

2. 그리고 부모 노드와 비교합니다. 만약 더 크다면 자리를 바꿉니다.

3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 과정을 반복(재귀)

 

과정

이 맥스 힙에서 9를 추가해보겠습니다!
      8      Level 0
    6   3    Level 1  
   4 2 1     Level 2 

1. 맨 마지막에 원소를 넣습니다.

      8      Level 0
    6   3    Level 1  
   4 2 1 9   Level 2 

2-1. 부모 노드와 비교합니다. 3보다 9가 더 크니까! 둘의 자리를 변경합니다.

      8      Level 0
    6   3    Level 1  
   4 2 1 9   Level 2 

      8      Level 0
    6   9    Level 1  
   4 2 1 3   Level 2 

2-2. 다시 부모 노드와 비교합니다. 8보다 9가 더 크니까! 둘의 자리를 변경합니다.

      8      Level 0
    6   9    Level 1  
   4 2 1 3   Level 2 

      9      Level 0
    6   8    Level 1  
   4 2 1 3   Level 2 

3. 가장 위에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삽입했습니다!

      9      Level 0
    6   8    Level 1  
   4 2 1 3   Level 2

 

최대 힙 - 삽입 시간복잡도

- 결국 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올리고 있다.

- 맥스 힙의 원소 추가는 O(log(N)) 만큼의 시간복잡도를 가진다고 분석할 수 있다.

 

최대 힙 - 추출 알고리즘

- 최대 힙에서 원소를 추출하는 방법은 최댓값, 루트 노드를 삭제하는 것이다.

- 스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수는 없다.

- 또한 맥스 힙에 원소를 추가했던 것과 마찬가지로 원소를 삭제할때도 힙의 규칙이 지켜져야 한다.

- 아래와 같은 방법으로 하면 된다.

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.

3. 변경된 노드와 자식 노드들을 비교한다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꾼다.

4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바당게 도달하지 않을 때까지 3. 과정을 반복한다.

5. 2에서 제거한 원래 루트 노드를 반환한다.

 

과정

이 맥스 힙에서 원소를 제거해보겠습니다! (항상 맨 위의 루트 노드가 제거 됩니다.)
      8      Level 0
    6   7    Level 1  
   2 5 4 3   Level 2 

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

      8      Level 0
    6   7    Level 1  
   2 5 4 3   Level 2 

      3      Level 0
    7   6    Level 1  
   2 5 4 8   Level 2 

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제합니다. 
이 값이 기존 맥스힙에 있던 가장 큰 값입니다. 따라서 이 값을 마지막에는 반환해줘야 합니다!

      3      Level 0
    6   7    Level 1  
   2 5 4 X   Level 2 

3-1. 변경된 노드를 더 큰 자식 노드와 비교해야 합니다. 
우선 부모와 왼쪽 자식을 비교합니다. 그리고 부모와 오른쪽 자식을 비교합니다.
그리고 부모 보다 큰 자식 중, 더 큰 자식과 변경해야 합니다.
왼쪽 자식인 6과 오른쪽 자식인 7 중에서 7이 더 크고, 부모인 3보다 크니까 둘의 자리를 변경합니다.

      3      Level 0
    6   7    Level 1  
   2 5 4     Level 2 

      7      Level 0
    6   3    Level 1  
   2 5 4     Level 2 

3-2. 다시 자식 노드와 비교합니다. 
우선 부모와 왼쪽 자식을 비교합니다.
왼쪽 자식인 4는 부모인 3보다 더 크니까 둘의 자리를 변경합니다.

      7      Level 0
    6   3    Level 1  
   2 5 4     Level 2 

      7      Level 0
    6   4    Level 1  
   2 5 3     Level 2 


4. 가장 아래 레벨에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삭제했습니다!

      7      Level 0
    6   4    Level 1  
   2 5 3     Level 2 

5. 그리고, 아까 제거한 원래 루트 노드, 8을 반환하면 됩니다!

 

최대 힙 - 추출 시간복잡도

- 결국 원소를 맨 위에 올려서 바닥까지 비교하면서 내리고 있다.

- 맥스 힙의 원소 삭제는 O(log(N)) 만큼의 시간 복잡도를 가진다고 분석 할 수 있다.