[자료구조] 힙(heap)

힙(Heap)

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

힙은 완전 이진트리이고, 자식 노드들이 특정한 성질을 가지고 정렬되어 있는 구조이다.

부모 노드가 자식 노드들보다 크다면 최대 힙(Max Heap)구조라고 하고, 부모 노드가 자식 노드들보다 작다면 최소 힙(Min Heap)구조라고 한다.

힙의 조건

1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
   • 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음
2. 완전 이진 트리 형태를 가짐

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

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

힙의 동작

• 힙은 대표적으로 정렬 알고리즘 , 우선순위 큐 라는 추상 자료형을 구현하는데 사용된다.
• 우선 힙의 정렬을 구현해보자

힙 정렬

def heapify(tree, index, tree_size): # 주어진 배열(tree)에서
    """배열의 해당 인덱스를 heap으로 만드는 함수"""

    # 왼쪽 자식 노드의 인덱스와 오른쪽 자식 노드의 인덱스
    left_child_index = 2 * index
    right_child_index = 2 * index + 1

    largest = index  # 일단 부모 노드의 값이 가장 크다고 설정

    # 왼쪽 자식 노드의 값과 비교
    if 0 < left_child_index < tree_size and tree[largest] < tree[left_child_index]:
        largest = left_child_index

    # 오른쪽 자식 노드의 값과 비교
    if 0 < right_child_index < tree_size and tree[largest] < tree[right_child_index]:
        largest = right_child_index
    
    if largest != index: # 부모 노드의 값이 자식 노드의 값보다 작으면
        tree[index], tree[largest] = tree[largest], tree[index] # 부모 노드와 최댓값을 가진 자식 노드의 위치를 바꿔준다
        heapify(tree, largest, tree_size)  # 자리가 바뀌어 자식 노드가 된 기존의 부모 노드를 대상으로 heap 과정을 거친다

• 해당 heapify 동작을 마지막 노드부터 루트 노드까지 수행하면 전체 트리가 힙 조건을 만족한다.

def heapsort(tree):
    """힙 정렬 함수"""
    tree_size = len(tree)

    # 마지막 인덱스부터 처음 인덱스까지 heapify를 호출한다 -> 받은 리스트 (tree)를 힙으로 만듦
    for index in range(tree_size, 0, -1):
        heapify(tree, index, tree_size) -> tree는 힙이 된다.

    # 마지막 인덱스부터 처음 인덱스까지
    for i in range(tree_size-1, 0, -1):
        tree[1], tree[i] = tree[i], tree[1]
        heapify(tree, 1, i)
        '''가장 큰 수인 루트노드 tree[1]과 마지막 노드를 교환 하면
        마지막 노드가 가장 큰 수가 됌.
        그 다음 마지막 인덱스를 제외한 나머지 리스트로 같은 과정을 반복하면
        높은 숫자부터 쌓여 오름차순으로 정렬되게 된다.'''

우선순위 큐

• 힙에 데이터를 삽입
• 힙 속성을 유지하도록 삽입한 데이터를 조정
• 첫번째 루트 노드는 항상 가장 큰(우선순위가 높은) 노드임

def reverse_heapify(tree, index):
    """삽입된 노드를 힙 속성을 지키는 위치로 이동시키는 함수"""
    parent_index = index // 2  # 삽입된 노드의 부모 노드의 인덱스 계산
    if 0 < parent_index < len(tree) and tree[index] > tree[parent_index]:
          tree[index], tree[parent_index] = tree[parent_index], tree[index]  # 부모 노드와 삽입된 노드의 위치 교환
          reverse_heapify(tree, parent_index)  # 바뀐 부모 노드에서 다시 reverse_heapify 호출

class PriorityQueue:
    """힙으로 구현한 우선순위 큐"""
    def __init__(self):
        self.heap = [None]  # 파이썬 리스트로 구현한 힙


    def insert(self, data):
        """삽입 메소드"""
        self.heap.append(data)
        reverse_heapify(self.heap, len(self.heap)-1)


    def __str__(self):
        return str(self.heap)


# 실행 코드
priority_queue = PriorityQueue()

priority_queue.insert(6)
priority_queue.insert(9)
priority_queue.insert(1)
priority_queue.insert(3)
priority_queue.insert(10)
priority_queue.insert(11)
priority_queue.insert(13)

print(priority_queue)

---------------------------------

>>> [None, 13, 9, 11, 3, 6, 1, 10]

우선순위 큐에서 우순순위 데이터 추출

• 루트 노드와 마지막 노드를 바꾼다.
• 마지막 노드(가장 큰 수)를 변수에 저장
• root 노드에 heapify 함수를 호출하여 힙 속성 부여
• 변수에 저장한 데이터를 추출

import heapify
import reverse_heapify

class PriorityQueue:
    """힙으로 구현한 우선순위 큐"""
    def __init__(self):
        self.heap = [None]  # 파이썬 리스트로 구현한 힙

'''현재 우선순위 큐를 전에 만든 [None, 13, 9, 11, 3, 6, 1, 10] 라고 가정'''
    def extract_max(self):
        """최고 우선순위 데이터 추출 메소드"""
        len(self.heap) - 1 = last_node_idx
        
        self.heap[1], self.heap[last_node_idx] = \
        self.heap[last_node_idx], self.heap[1]# root 노드와 마지막 노드의 위치 바꿈
        
        max_value = self.heap.pop()  # 힙에서 마지막 노드 추출(삭제)해서 변수에 저장
        
        heapify(self.heap, 1, len(self.heap))  # 새로운 root 노드를 대상으로 heapify 호출해서 힙 속성 유지
        return max_value  # 최우선순위 데이터 리턴

시간 복잡도

• 힙의 삽입 : 노드 삽입 O(1) + 그 노드를 힙으로 만드는 과정 최대 O(log(n)) = 총 O(lg(n))

• 힙의 추출 : root노드와 마지막 노드 위치바꿈 O(1) + 마지막 노드 변수에 저장(pop) O(1)

  ​ + 새로운 root에 힙속성 부여 O(lg(n)) + 변수 리턴 O(1) = 총 O(lg(n))

	데이터 삽입	데이터 추출
정렬된 동적 배열	O(lg(n)) - 이진탐색 이용	O(1)
정렬된 더블 링크드 리스트	O(n)	O(1)
힙	O(lg(n))	O(lg(n))

• 삽입에는 힙이 효율적
• 추출에는 링크드 리스트 또는 동적 배열이 효율적