힙(Heap)

---

📒힙은 이진트리의 한 종류로 루트노드가 언제나 최댓값또는 최솟값을 가집니다.(최대 힙, 최소 힙 이라고 한다.) 그리고 트리는 완전이진트리여야합니다.

최대 힙

---

여기서는 최대 힙만 구현해 보았습니다.

최대 힙을 구현하기 전에 성질과 특징에 대해 얘기하고자 합니다.

최대 힙의 성질

1. 루트 노드가 항상 최댓값을 가진다.
2. 완전 이진 트리이다.
3. 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.

최대 힙의 특징

부가의 제약 조건, 즉 완전 이진 트리 (complete binary tree) 여야 한다는 제약 때문에, n 개의 노드로 이루어진 최대 힙의 높이 (깊이) 는 log(n) + 1 (에서 소수 부분은 버림) 로 정해집니다. 이 성질 때문에 데이터 원소의 삽입/삭제 연산의 실행 시간은 언제나 log(n) 에 비례합니다. 따라서, 어떤 최대 힙이 존재할 때, 이 힙으로부터 반복적으로 루트 노드를 삭제하면 (서 데이터 원소들을 꺼내면) 루트 노드에 들어 있는 키가 힙 내에서 최대임이 보장되어 있으므로 데이터를 내림차순으로 정렬할 수 있고, 이 정렬에 소요되는 시간 또한 log(n) 에 비례합니다.
힙이 항상 완전 이진 트리라는 성질은 트리의 표현에 있어서도 이점을 제공합니다. (동영상 강의에서 소개될) 규칙에 따라 노드들에 번호를 매기면, 이 번호 순서로 이루어진 선형 배열에 트리를 표현할 수 있습니다. 또한, 완전 이진 트리이므로 노드의 추가와 삭제는 배열의 맨 마지막 원소에서만 일어납니다.

최대 힙 구현

최대 힙 구현에 있어서 배열을 이용한 이진트리로 구현했습니다.

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

    def insert(self, item):
        # 흰트 - python에서 두 변수의 값 바꾸기
        # a = 3, b = 5
        # a, b  = b, a
        self.data.append(item)

        index = len(self.data) -1

        while index != 1:
            numOfParentNode = index//2
            print(numOfParentNode)

            if self.data[numOfParentNode] < self.data[index]:
                self.data[numOfParentNode], self.data[index] = self.data[index], self.data[numOfParentNode]
                index = numOfParentNode
            else:
                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) # 말단으로 가있는 Max 값을 제거
            self.maxHeapify(1) # 다시 MaxHeap 모양으로 정리

        else:
            data = None
        return data

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

---