자료구조 - 힙

1. 힙(Heap)이란?

• 힙 : 데이터의 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
  
  • 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 (자식은 2개까지)
• 사용 이유
  • 배열에 데이터 넣고, 최대값과 최소값 찾으려면 O(n)이 걸림
  • 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값 찾으면 O(logN)이 걸림
  • 우선순위 큐와 같이 최대값 또는 최소값 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용 됨

2. 힙(Heap) 구조

• 힙은 최대값을 구하기 위한 구조(최대 힙, Max Heap)와, 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류할 수 있음
• 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조임
  1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
     • 최소 힙은 반대, 각 노드 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같음 (최소 힙의 경우)
  2. 완전 이진 트리 형태를 가짐 (데이터를 넣을 때 항상 왼쪽부터 채워가는 구조)

힙과 이진 탐색 트리의 공통점과 차이점

• 공통점 : 힙과 이진 탐색 트리는 모두 이진 트리임(자식 노드 최대 2개)
• 차이점 :
  • 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
  • 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
  • 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
    • 힙의 왼쪽 및 오른쪽 자식 노드 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음
  • 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨(목적이 다름)

3. 힙(Heap) 동작

 

힙에 데이터 삽입하기 - 기본 동작

• 힙은 완전 이진 트리이므로 삽입할 노드는 기본적으로 왼쪽 최하단 노드부터 채워지는 형태로 삽입

힙에 데이터 삽입하기 - 삽입할 데이터가 힙의 데이터보다 클 경우(Max Heap의 예)

• 우선 데이터를 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채움
• 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함(swap)

힙에 데이터 삭제하기 (Max Heap의 예)

• 보통 삭제는 최상단 노드 (root 노드)를 삭제하는 것이 일반적
  • 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임
• 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드)를 root 노드로 이동
• root 노드의 값이 Child Node보다 작을 경우, root 노드의 Child Node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함(swap)

4. 힙(Heap) 구현

 

힙과 배열

• 일반적으로 힙 구현시 배열 자료구조 사용함
• 배열은 인덱스가 0번부터 보통 시작하지만, 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정(구현 수월함)
  • 부모 노드 인덱스 번호(Parent Node's index) = 자식 노드 인덱스 번호(Child Node's index) // 2
  • 왼쪽 자식 노드 인덱스 번호(Left Child Node's index) = 부모 노드 인덱스 번호(Parent Node's index) * 2
  • 오른쪽 자식 노드 인덱스 번호(Right Child Node's index) = 부모 노드 인덱스 번호(Parent Node's index)*2+1

▼ 힙 데이터 삽입 구현(Max Heap의 예)

 

힙 삽입 클래스 구현

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None) #0번 인덱스는 비워놓음
        self.heap_array.append(data)
    
    #상위 노드랑 바꿔야 하는지 root 노드라서 바꿀 필요가 없는지 판단
    def move_up(self, inserted_idx):
        if inserted_idx <= 1:
            return False

        parent_idx = inserted_idx // 2
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        else:
            return False
    
    def insert(self, data):
        if len(self.heap_array ) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True
#append라는 Method가 리스트 맨 끝에 추가하는 형식이라 최하단 노드에 노드를 추가하는 기능이 자동으로 됨
        self.heap_array.append(data) 

        inserted_idx = len(self.heap_array) - 1 #인덱스 찾기

        while self.move_up(inserted_idx): #True면 계속 바꿔주기
            parent_idx = inserted_idx // 2 #부모 노드 찾기
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
            #부모와 자식노드를 바꾸는 SWAP 기능
            inserted_idx = parent_idx
            
        return True 

 

힙 데이터 삭제 구현(Max Heap의 예)

• 힙 클래스 구현4 - delete 1
• 보통 삭제는 최상단 노드(root 노드)를 삭제하는 것이 일반적임
  • 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것
• 삭제해서 자리가 바뀐 노드의 자식이 둘이면 자식끼리 서로 비교해서 큰 값을 찾은 다음 큰 노드와 부모노드를 비교해서 작으면 자리를 바꿔준다

 

힙 삭제 클래스 구현

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None) #0번 인덱스는 비워놓음
        self.heap_array.append(data)

    def move_down(self, popped_idx):
        left_child_popped_idx = popped_idx * 2      #왼쪽 노드가 없으면 끝남(완전이진트리이기 때문)
        right_child_popped_idx = popped_idx * 2 + 1

        # case1: 왼쪽 자식 노드도 없을 때
        if left_child_popped_idx >= len(self.heap_array):
            return False
        # case2: 오른쪽 자식 노드만 없을 때
        elif right_child_popped_idx >= len(self.heap_array):
            if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                return True
            else:
                return False
        # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
        else :
            if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]: #왼쪽이 더 클 때
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    return True
                else:
                    return False
            else:
                if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                    return True
                else:
                    return False


    def pop(self):
        if len(self.heap_array) <=1:
            return None

        returned_data = self.heap_array[1]
        self.heap_array[1] = self.heap_array[-1] #배열에 -1하면 맨 끝에 있는 데이터를 나타냄
        del self.heap_array[-1] #맨 끝에 있는 데이터 공간을 지워줌

        while self.move_down(popped_idx):
            left_child_popped_idx = popped_idx * 2
            right_child_popped_idx = popped_idx * 2 + 1

            # case2: 오른쪽 자식 노드만 없을 때
            if right_child_popped_idx >= len(self.heap_array):
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                    popped_idx = left_child_popped_idx

            # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
            else :
                if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
                    if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = left_child_popped_idx
                else:
                    if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = right_child_popped_idx

        return returned_data

 

힙 클래스 구현

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None) #0번 인덱스는 비워놓음
        self.heap_array.append(data)

        #상위 노드랑 바꿔야 하는지 root 노드라서 바꿀 필요가 없는지 판단
    def move_up(self, inserted_idx):
        if inserted_idx <= 1:
            return False

        parent_idx = inserted_idx // 2
        
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        else:
            return False
    
    def insert(self, data):
        if len(self.heap_array ) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True

#append라는 Method가 리스트 맨 끝에 추가하는 형식이라 최하단 노드에 노드를 추가하는 기능이 자동으로 됨
        self.heap_array.append(data) 

        inserted_idx = len(self.heap_array) - 1 #인덱스 찾기

        while self.move_up(inserted_idx): #True면 계속 바꿔주기
            parent_idx = inserted_idx // 2 #부모 노드 찾기
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
            #부모와 자식노드를 바꾸는 SWAP 기능
            inserted_idx = parent_idx
            
        return True 

    def move_down(self, popped_idx):
        left_child_popped_idx = popped_idx * 2      #왼쪽 노드가 없으면 끝남(완전이진트리이기 때문)
        right_child_popped_idx = popped_idx * 2 + 1

        # case1: 왼쪽 자식 노드도 없을 때
        if left_child_popped_idx >= len(self.heap_array):
            return False
        # case2: 오른쪽 자식 노드만 없을 때
        elif right_child_popped_idx >= len(self.heap_array):
            if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                return True
            else:
                return False
        # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
        else :
            if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]: #왼쪽이 더 클 때
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    return True
                else:
                    return False
            else:
                if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                    return True
                else:
                    return False


    def pop(self):
        if len(self.heap_array) <=1:
            return None

        returned_data = self.heap_array[1]
        self.heap_array[1] = self.heap_array[-1] #배열에 -1하면 맨 끝에 있는 데이터를 나타냄
        del self.heap_array[-1] #맨 끝에 있는 데이터 공간을 지워줌

        while self.move_down(popped_idx):
            left_child_popped_idx = popped_idx * 2
            right_child_popped_idx = popped_idx * 2 + 1

            # case2: 오른쪽 자식 노드만 없을 때
            if right_child_popped_idx >= len(self.heap_array):
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                    popped_idx = left_child_popped_idx

            # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
            else :
                if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
                    if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = left_child_popped_idx
                else:
                    if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = right_child_popped_idx

        return returned_data

 

5. 힙(Heap) 시간 복잡도

• depth(트리의 높이)를 h라고 표기한다면
• n개의 노드를 가지는 heap 데이터 삽입 또는 삭제 시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 h = log2n에 가까우므로, 시간 복잡도는 O(logN)
  • 참고 : 빅오 표기법에서 logN에서의 log의 밑은 2이다
  • 한번 실행시마다, 50%의 실행할 수도 잇는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미한다