파이썬) 최대 힙(Heap)

힙이란 이진 트리의 한 종류로 루트 노드가 언제나 최댓값 또는 최솟값을 가지는 완전 이진 트리이다.

또한 어느 노드를 루트 노드로 하는 서브트리도 모두 최대 힙이여야 한다. (재귀적으로도 정의됨)

 

이진 탐색 트리와 최대힙을 비교하자면 이진 탐색 트리에서는 원소들이 완전히 크기 순서대로 정렬되어 있다. 따라서 중위 순회를 하면 데이터를 정렬된 순서로 뽑아낼 수 있다. 하지만  최대 힙은 완전히 크기 순서대로 정렬되어 있지는 않다. 따라서 트리를 순회함으로써 데이터를 정렬할 수는 없다. 또한, 이진 탐색 트리에서는 루트 노드로부터 시작하여 특정 원소를 빠르게 검색할 수 있는 반면, 최대 힙은 이러한 탐색 연산을 제공할 수 없다는 특징이 있다.

 

최대 힙은 완전 이진 트리여야 한다는 조건이 있기 때문에 데이터 원소 삽입/삭제 연산의 시간 복잡도는 O(logn)이다.

 

최대힙을 배열을 이용해 표현하면 다음과 같다.

위와 같은 최대힙에 루트 노드부터 같은 레벨의 노드는 왼쪽부터 번호를 순서대로 매기면 위와 같다.  

노드 번호 m을 기준으로 아래와 같은 특징을 가지고 있다.

• 왼쪽 자식의 번호 : 2*m
• 오른쪽 자식의 번호 : 2*m+1
• 부모 노드의 번호 : m//2

완전 이진 트리의 성질을 가지고 있으므로 노드의 추가/삭제는 마지막 노드에서만 가능하다.

따라서 배열로 표현하면 0번째 index제외한 나머지 1~10을 배열안에 넣을 수 있다.

 

 

배열로 정의 된 최대힙을 이용해 삽입 연산을 구현하면 다음과 같다.

만약 위와 같은 최대힙에 30을 삽입한다고 가정하면 우선 30을 트리의 마지막 자리에 저장한다.

 

 

부모 노드와 크기를 비교했을 때 30은 12보다 크므로 자리를 서로 바꾼다.

 

마찬가지로 20과 30을 맞바꾼다. 

 

이러한 알고리즘을 코드로 구현하면 다음과 같다.

class MaxHeap:

    def __init__(self):
        self.data = [None]  # 빈 최대힙 리스트 생성

    def insert(self, item):
        self.data.append(item) # 삽입할 원소를 최대힙 리스트에 추가
        a=len(self.data)-1 
        while a>1:
            if self.data[(a//2)] < self.data[a]:  # 삽입할 원소와 부모 노드 원소 크기 비교
                self.data[a],self.data[(a//2)]=self.data[(a//2)],self.data[a]
                a=a//2
            else : break

특정 노드 번호 m이 있다면 부모 노드는 m//2인 것을 이용해 self.data[(a//2)] < self.data[a]처럼 삽입할 원소와 부모 노드의 원소를 비교한다. 만약 부모 노드가 더 작다면 두 위치를 맞바꾼다. if절의 조건이 a>1인 이유는 배열로 구현한 최대힙의 리스트 인덱스는 1번부터 시작하기 때문이다.