힙

최대 힙의 성질

최대 힙은 완전히 크기 순서대로 정렬되어 있지는 않다. 따라서 탐색 연산은 지원하지 않는다.

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

배열을 이용한 이진트리의 표현

왜 트리와는 다르게 heap은 배열을 사용하여 표현할까?

• Tree를 구현할 때 흔히 사용하는 linked list 방식으로 하면 마지막 인덱스에 데이터 추가하는 일이 쉽지 않다.
  • 마지막 리스트를 찾기위한 연산의 복잡도는 트리의 높이만큼 탐색해야하기 때문에 O(h)임.
• 힙은 완전 이진트리라는 것이 보장된 형태이 기 때문에, 마지막 레벨을 제외한 모든 레벨의 노드가 가득 채워져있다. 따라서 완전 이진트리의 삽입은 배열 끝 인덱스에 append해주는 것과 같으며, 이후 힙의 성질에 부합하도록 크기를 비교한다.

 

규칙에 따라 노드들에 번호를 매기면, 이 번호 순서로 이루어진 선형 배열에 트리를 표현할 수 있다.

완전 이진 트리이므로 노드의 추가와 삭제는 배열의 맨 마지막 원소에서만 일어난다.

힙의 원소 삽입 구현

이 과정을 루트 노드에 도달할 때까지 또는 더이상 맞바꿀 필요가 없을 때까지 반복

1. 선 맨 마지막 노드에 주어진 데이터를 임시로 붙인 뒤에 이 원소를 부모 노드의 키와 비교한다.
2. 더 큰 경우에는 그 부모와 위치를 맞바꾼다.

노드의 삽입에서는 자신의 부모 노드를 찾아서 자리를 바꿀지를 결정하는데 부모 노드는 오직 하나만 있거나 아니면 없다(없는 경우 : 루트노드). 따라서 힙의 삭제보다 간단하다.

실습

class MaxHeap:

    def __init__(self):
        self.data = [None]
  
    def insert(self, item):
        lst = self.data
        lst.append(item)
        
        m = lst.index(item)
        p = m // 2
        
        while(p != 0 and lst[p]<lst[m]):
            lst[m] , lst[p] = lst[p] , lst[m] 
            m = lst.index(lst[p])
            p = m//2
        

def solution(x):
    m = MaxHeap()
    
    m.insert(1)
    m.insert(20)
    m.insert(30)
    m.insert(4)
    
    print(m.data)

최대 힙 (Max Heap) 에서 원소의 삭제

• 최대 힙에서의 원소 삭제는 항상 루트 노드에서 이루어진다. 최댓값을 순서대로 뽑아 내는 데 관심이 있기 때문이다.

삭제 구현

• 우선은 루트 노드의 데이터를 꺼낸다.
• 가장 오른쪽 노드를 루트 노드에 놓는다.

루트 노드와 자식 노드를 더이상 바꿀 필요가 없거나 리프 노드에 도달할 때까지 이 과정을 반복한다.

삭제 연산에서는 자식들 중 더 큰 키 값을 가지는 노드를 찾는데 자식이 둘 있는 경우, 하나만 있는 경우, 아니면 없는 경우 (리프 노드) 의 세 가지를 구별한다.

1. (일시적으로 위치가 올바르지 않은) 노드는 루트 노드에서 시작해서 아래로 아래로 내려간다.
2. 자식들 중 더 큰 값을 가지는 노드와 자리를 바꾼다

실습

class MaxHeap:

    def __init__(self):
        self.data = [None,20,6,10,5,3,4]

    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 child) 의 인덱스를 계산합니다.
        left = 2*i

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = i*2+1

        biggest = i
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[left] > self.data[biggest]:
        # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            biggest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right < len(self.data) and self.data[right] > self.data[biggest] :
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            biggest = right

        if biggest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[biggest] , self.data[i] = self.data[i] , self.data[biggest]

            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(biggest)

m = MaxHeap()
print(m.remove())
print(m.remove())