[Python] 최대/최소 힙

힙이란?

- 완전 이진트리의 한 종류이며, 느슨한 정렬을 이루고 있는 자료구조.

- 느슨한 정렬이란 리프 노드들 간에는 큰 특징이 없으며 루트 - 서브 간의 위계만 존재한 정렬을 의미함.

- 최대/최소 힙 두 형태가 있으며 느슨한 정렬을 이루고 있기 때문에 순회나 특정 원소가 필요한 연산은 적절치 않음.

- 우선순위 큐/힙정렬 등의 알고리즘에 주로 사용됨.

 

추상적 구현

- 힙 클래스 생성 후 값 추가, 삭제의 기능을 갖는 함수 부여.

- 값 추가하는 함수 : 트리의 맨 끝에 값 append, 마지막 인덱스 // 2 값이 0보다 클 동안 값 비교.

- 값 제거하는 함수 : 특정 값은 제거 불가능, 루트 노드 값을 제거, 맨 끝 값을 루트 노드로 올려준 뒤, heapify()를 통해 정리.

- heapify() : 힙을 느슨한 정렬로 만들어 주는 함수, 노드 값을 인수로 받으며 왼쪽, 오른쪽 자식 간의 크기 비교를 통해 재귀적으로 구현.

 

# PYTHON CODE

class Max_heap:

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

    def plus(self, value):
        self.data.append(value)
        x = len(self.data)
        while x // 2 > 0:
            if self.data[x] > self.data[x // 2]:
                self.data[x], self.data[x // 2] = self.data[x // 2], self.data[x]
            else:
                break
            x = x // 2

    def remove(self):
        x = len(self.data)
        if x > 1:
            value = self.data.pop()
            self.data[1] = value
            self.max_heapify(1)

    def max_heapify(self, i):
        left = i * 2
        right = i * 2 + 1
        biggest = i

        if left < len(self.data) and self.data[left] > self.data[biggest]:
            smallest = left
        if right < len(self.data) and self.data[right] > self.data[biggest]:
            smallest = right
        if biggest != i:
            self.data[i], self.data[biggest] = self.data[biggest], self.data[i]
            self.max_heapify(biggest)

최소 힙 또한 구현 양상은 같다. 부등호 방향 같은 것들만 고려하면 유사한 아이디어로 구현할 수 있다.