[Python] Max Heap

Max Heap(최대 힙)의 삽입 알고리즘과 시간복잡도에 대해 공부해 봅니다.

---

 

Heap은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(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)

 

 

MaxHeap  -  '삽입' 알고리즘

 

Heap의 규칙

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

 

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

 

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

 

 

 

MaxHeap  -  '삽입' 시간복잡도

 

 

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

완전 이진트리의 최대 높이는 O(log(N)) 이기 때문에

반복하는 최대 횟수도 O(log(N)) 이다.

 

즉! Max Heap의 원소 추가는 O(log(N)) 만큼의 시간 복잡도를 가진다.

 

 

최대 힙 삽입 구현 ▽

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self.items) - 1
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2