[자료구조] Heap 기초 개념 알아보기(python)

[자료구조] Heap 기초 개념 알아보기(python)

 

 

살펴볼 주요 개념:

- 힙이란?

- 힙을 충족하는 트리 형태

- 힙 직접 구현

 

1. 힙이란?

힙 성질(heap property)을 만족하는 이진트리(Binary Tree)이다.

 

 

* 힙 성질

- 모양성질 : 레벨 별로 모든 노드가 꽉 차있고, 마지막 레벨의 노드만 왼쪽에서부터 차있는 형태

- heap 성질 : 모든 부모노드의 key값이 자식노드의 key값보다 작지 않다.

 

힙성질을 만족하지 않는 트리

 

 

 

힙성질을 만족하는 트리

 

힙 성질을 만족하는 트리를 리스트화 해서 표현하면 다음과 같다.

A = [15, 12, 6, 11, 10, 2, 3, 1, 5]

 

루트 노드에는 리스트에서 가장 큰 값이다.

힙은 insert와  remove(최대값 삭제), maxHeapify 연산을 지원한다.(max heap)

각각의 시간 복잡도는 O(logN), O(1), O(logN)이다.

 

2. 힙을 충족하는 트리 형태

그러면 위에서 힙 성질을 만족하지 않는 트리를 어떻게 성질을 만족하게 만들었을까?

밑에서 직접 클래스를 구현하기 전에 과정을 살펴보면 다음과 같다. 

 

왼쪽 가장 아래의 부모노드와 자식노드부터 확인하면서 전체를 돌아보는 것이다.

1번 순서의 트리를 리스트로 나타내면 아래와 같다.

A = [2, 8, 6, 1, 10, 15, 3, 12, 11]

A[3]부터 시작해서 각각의 왼쪽 자식노드(A[3 * 2 + 1])와 오른쪽 자식노드(A[3 * 2 + 2])와 값을 비교한다.

계속적으로 살펴보면 A[k]의 자식노드는 A[k * 2 + 1], A[k * 2 + 2]인 것이다.

(이 과정은 아래 MaxHeap 클래스의 maxHeapify 메소드의 연산 과정이다.)

 

이렇게 전체 노드를 아래부터 바꾸어 나가면 전체 트리가 힙 성질을 만족하게 되는 결과를 얻을 수 있다.

 

3. MaxHeap 직접 구현

class MaxHeap:

    def __init__(self):
        self.data = [None]


    def insert(self, item):
        self.data.append(item)
        i = len(self.data) - 1
        while i > 1:   # 최상위 루트 노드까지 탐색
            if self.data[i] > self.data[(i // 2)]: # 부모노드 보다 크다면 서로의 자리를 바꿔줌. 
                self.data[i], self.data[(i // 2)] = self.data[(i // 2)], self.data[i]
                i = i // 2 # 그 위의 레벨을 탐색하기 위해 //2
            else: # 부모노드 보다 크지 않다면 while문 탈출
                break

    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data


    def maxHeapify(self, i):
        left = 2 * i
        right = (2 * i) + 1
        smallest = i        
        if left < len(self.data) and self.data[i] < self.data[left]: # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 무엇보다 큰지 판단.                     
            smallest = left  # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가짐       
        if right < len(self.data) and self.data[i] > self.data[right]: # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단.      
            smallest = right  # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가짐.
        if smallest != i:    
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i] # 현재 노드(인덱스 i)와 최댓값 노드 (왼쪽 아니면 오른쪽 자식)를 교체
            self.maxHeapify(smallest) # 재귀적 호출을 활용하여 최대 힙의 성질을 만족할 때까지 트리를 정리.