[Week2 자료구조/알고리즘] TIL 4일차 - 힙과 추가문제

1) 힙(Heap)

힙은 완전 이진트리 중 하나로 루트 노드가 전체 트리의 최솟값(=최솟값 힙)이나 최댓값(=최댓값 힙)을 갖는 자료구조이다.

어떤 노드에서도 왼쪽 서브트리, 오른쪽 서브트리도 모두 최소 혹은 최대 힙이여야 하므로 재귀적으로 정의 할 수 있다.

 

저번 시간에 배웠던 이진 탐색 트리와 비교해 보면

• 키의 크기순으로 정렬되어 있지 않고
• 이 때문에 빠른 탐색도 어려우며
• 완전이진트리이기 때문에 삽입, 삭제가 마지막 노드에서 이루어져야 한다.

 

자료구조의 해당 특성에서 비롯하여 정의되는 함수는 다음과 같다.

• insert(item) : item을 마지막 노드에 삽입한뒤, 루트 노드와의 크기비교를 통해 적절한 위치를 찾아나간다.
• remove() : 루트 노드를 삭제한 뒤, 알맞은 노드를 해당 자리로 이동시킨다.

 

구현

배열을 이용해서 구현해 보자

→ 완전 이진트리이기 때문에 삽입 삭제가 마지막 노드에서만 이루어지므로 배열 자료구조를 이용하는 것이 좋다.

 

인덱스 0의 원소를 None으로 초기화 하면, 부모노드, 자식노드의 인덱스는 다음과 같다.

• 부모 노드의 인덱스 : n
• 왼쪽 자식 노드의 인덱스 : 2n
• 오른쪽 자식 노드의 인덱스 : 2n+1

 

함수

• insert(item) : item을 삽입
  • 우선 item값은 마지막 위치에 삽입한뒤 → 부모 노드보다 크면 위로 이동시킨다.
  • 최악 복잡도 O(log n) 

cf) 파이썬에서는 두 변수의 값은 바꿀때 한번에 바꿀 수 있다.

• a, b=b, a

코드

class MaxHeap:

    def __init__(self):
        self.data = [None]
    def insert(self, item):
        self.data.append(item)
        nowidx = len(self.data) -1
        while nowidx >1:
            if self.data[nowidx] > self.data[nowidx//2]:
                self.data[nowidx],self.data[nowidx//2] = self.data[nowidx//2],self.data[nowidx]
                nowidx=nowidx//2
            else:
                break

• remove() : 삭제
  • 루트 노드 삭제한뒤, 알맞은 노드를 찾아 해당 새로운 루트 노드로 삼는다.
    • 트리의 마지막 노드를 임시로 루트 노드에 위치하고 자식 노드와 비교(둘중에 더 큰 값과 바꾸기)
  • 최악 복잡도 2*O(log n)

코드

class MaxHeap:

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


    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 = 
i*2

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

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

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

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

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


def solution(x):
    return 0