트리 구조 - Heap

트리 구조 간단 정리

트리 구조 : 노드가 부모-자식 관계를 가지는 자료구조
(연결 리스트는 자식이 최대 1개인 트리 구조라고 볼 수 있다)

• Root 노드 : 트리의 첫번째 노드
• Leaf 노드 : child노드가 없는 노드
• Edge(or link) : 노드와 노드를 잇는 연결

트리의 높이(height) : root에서 가장 깊은 leaf까지 edge 개수
레벨(level) : root를 레벨 0으로 하여 edge 하나씩 깊어질 때마다 레벨이 증가
즉, 가장 깊은 레벨 == height
형제 노드 : 같은 레벨에 있는 노드

경로(path) : 노드 v에서 노드 w를 잇는 경로
경로 길이 : 경로 상의 edge 개수

이진 트리(binary tree) : child노드가 최대 2개인 트리

완전 이진 트리 : 마지막 레벨을 제외하고, 그 상위 레벨이 모두 채워져 있으며, 마지막 레벨의 노드는 최대한 왼쪽에 있는 이진 트리

Heap

Heap 성질을 만족하는 완전 이진 트리.

여기서 Heap 성질이란, 모든 parent노드의 키값이 child노드의 키값보다 작지 않다, 혹은 크지 않다는 것이다. 따라서, root 노드는 트리의 키값 중 최댓값 or 최솟값이다.

(root가 최댓값이냐, 최솟값이냐에 따라 min_heap, max_heap으로 구분)

이 때문에, Heap은 최댓값, 혹은 최솟값을 연산하는데 특화된 자료구조이다.

연산 & 수행시간

heapifyUp : 노드 k를 parent노드와 비교하여 스왑 여부 결정을 반복
(최악의 경우 가장 깊은 레벨에서 root까지 이동할 수 있으므로 트리의 높이 h에 비례. 이때 2^h < N이므로, O(h) == O(logN))
heapifyDown : 노드 k를 child노드와 비교하여 스왑 여부 결정을 반복(O(logN))


☆makeHeap : 완전이진트리를 heap성질을 만족시키도록 변환(heapifyDown을 n번 반복하여 O(NlogN)이나, root에서 하위 레벨로 내려갈수록 heapifyDown 연산횟수가 감소하기 때문에 O(N)에 수렴)

insert : 트리의 마지막 노드에 키값을 추가하고, heap성질을 만족하도록 heapifyUp (O(LogN))

☆findMax : return 트리[0] (O(1))

deleteMax : 최댓값, 즉 트리[0]을 삭제하고, heapify (O(logN))

heapSort : 주어진 이진트리의 root와 마지막 leaf노드[n-1]부터 노드를 하나씩 스왑 후 heapify하여 root node가 트리의 최댓값이 되도록 정렬하는 연산 (O(NlogN))

Python 코드

파이썬은 heapq 모듈을 제공하여 리스트를 힙처럼 사용할 수 있지만, pseudocode를 참조하여 힙 연산을 직접 구현했다.

class Heap:
    def __init__(self,*keys): # A는 입력 받은 key값들을 리스트(트리)로 묶은 형태
        self.A = [*keys]
    
    def heapifyDown(self,k): # k노드를 그의 child노드와 비교하여 heapify
        while k*2+1 <= len(self.A) - 1: # k노드의 왼쪽 child노드 인덱스가 A 마지막 인덱스보다 크면, child가 없다. 즉 child가 존재할 경우 반복
            # child노드가 양쪽으로 다 있을 경우 노드 3개 비교
            if k*2+2 <= len(self.A) - 1: 
                L,R = k*2+1, k*2+2
                m = self.A.index(max(self.A[k],self.A[L],self.A[R])) # pa
                if k != m:
                    self.A[k],self.A[m] = self.A[m],self.A[k]
                    k = m        
                else: break
            # child 노드가 왼쪽 하나만 있을 경우 노드 2개만 비교
            else:                       
                L = k*2+1
                m = self.A.index(max(self.A[k],self.A[L]))
                if k != m:
                    self.A[k],self.A[m] = self.A[m],self.A[k]
                    k = m
                else: break
    
    def heapifyUp(self,k): # k노드를 parent노드와 비교하여 heapify
        while k > 0 and self.A[(k-1)//2] <= self.A[k]:
            self.A[k], self.A[(k-1)//2] = self.A[(k-1)//2], self.A[k]
            k = (k-1)//2
    
    def makeHeap(self):
        n = len(self.A)
        for k in range(n-1,-1,-1): # A의 마지막 leaf node부터 root node까지 역순으로 연산한다.
            self.heapifyDown(k)
        print("Heapify Complete!")
        return self.A
    
    def insert(self,key): # 마지막 노드에 새 key값을 append 후, parent 노드와 비교하여 heapify 여부 결정
        self.A.append(key)
        self.heapifyUp(self.A.index(key)) 
    
    def findMax(self): 
        return self.A[0]
    
    def deleteMax(self):
        if len(self.A) == 0:
            return None
        key = self.A[0]
        self.A[0], self.A[len(self.A)-1] = self.A[len(self.A)-1], self.A[0]
        self.A.pop()
        self.heapifyDown(0)
        return key
    
    def heapSort(self): # deleteMax와 유사하지만, pop을 안함
        if len(self.A) == 0:
            return None
        for k in range(len(self.A)-1,-1,-1):
            key = self.A[0]
            self.A[0], self.A[k] = self.A[k], self.A[0]
            self.heapifyDown(0)
        return self.A
    




data1 = Heap(2,8,6,1,10,15,3,12,11)
data1.makeHeap()			# Heapify Complete!
print(data1.A)				# [15, 12, 6, 11, 10, 2, 3, 1, 8]
data1.insert(14)			
print(data1.A)				# [15, 14, 6, 11, 12, 2, 3, 1, 8, 10]
data1.findMax()				# 15
data1.deleteMax()			
print(data1.A)				# [14, 12, 6, 11, 10, 2, 3, 1, 8]
data2 = Heap(2,8,6,1,10,15,3,12) 	# 마지막 레벨 노드가 홀수 개일 때
data2.makeHeap()
print(data2.A)				# [15, 12, 6, 8, 10, 2, 3, 1]
data3 = Heap(2,8,6,1,10,15,3,12,11)
print(data3.heapSort())			# [15, 11, 12, 10, 3, 8, 6, 1, 2]