데이터 구조 힙 ( Heap )

힙이란 ?

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 ( Complete Binary Tree )
  • 완전 이진 트리 : 노드를 삽입할 때, 최하단 왼쪽 노드부터 차례대로 삽입하는 트리!

)

힙을 사용하는 이유?

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 0(n) 이 걸린다.
• 이에 반해서, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, $ O(log n) $ 이 걸림
  O( log n ) : 문제를 해결하는 데 필요한 단계들이 연산마다 줄어듦
  O( n ) : 데이터 수와 연산횟수가 비례
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

힙(Heap) 구조

• 힙은 최대값을 구하기 위한 구조 ( 최대 힙, Max Heap ) 와 최소값을 구하기 위한 구조 ( 최소 힙, Min Heap ) 로 분류될 수 있다.
• 힙은 두가지 조건을 가지고 있는 자료 구조이다.
  1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다 ( 최대 힙의 경우 )
     • 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같다.
  2. 완전 이진 트리 형태를 가진다.

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

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

힙 동작

• 데이터를 힙 구조에 삽입, 삭제하는 과정을 그림을 통해 이해해 본다.
  동작
• 힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입!

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

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

4. 힙 구현

힙과 배열

• 일반적으로 힙 구현시 배열 자료구조를 활용함
• 배열은 인덱스가 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

힙 클래스 구현1 - 힙 클래스 구현 + 초기화 함수

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)


heap = Heap(1)
heap.heap_array

[None, 1]

힙 클래스 구현2 - insert1
인덱스 번호는 1번부터 시작하도록 변경

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)

    def insert(self, data):
        if len(self.heap_array) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True

        self.heap_array.append(data)
        return True   

힙 클래스 구현3 - insert2

• 삽입한 노드가 부모 노드의 값보다 클 경우, 부모 노드와 삽입한 노드 위치를 바꿈
• 삽입한 노드가 루트 노드가 되거나, 부모 노드보다 값이 작거나 같을 경우까지 반복

특정 노드의 관련 노드 위치 알아내기

• 부모 노드 인덱스 번호 (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

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)

    def move_up(self, inserted_idx):
        if inserted_idx <= 1: # 최상위 노드로 갔을 때, 더이상 비교 대상이 없어도 루프 종료
            return False

        parent_idx = inserted_idx // 2 # 값 비교해서 insert 된 값이 부모 값보다 크면 계속 swap 루프 돌림.
        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: # 힙 배열 길이가 0 이면 무조건 앞에 None 하나 넣어준다 ( 인덱스를 1부터 시작하기 위해서 )
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True

        self.heap_array.append(data)

        inserted_idx = len(self.heap_array) - 1 # 들어간 인덱스 값이 힙 배열 길이보다 하나 작다.

        while self.move_up(inserted_idx):
            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]
            inserted_idx = parent_idx # 값을 바꿔주고 인덱스 값도 바꿔준다 ( 참조값 변경 ) 하나씩 상위노드로 올라감

        return True