[자료구조] 힙(Heap)

힙(Heap)

우선순위 큐(Priority Queue)

힙을 보기전에 먼저 우선순위 큐를 살펴보도록 하겠습니다.
우선순위 큐는 각각의 원소가 우선순위를 가지고 있으며, 우선순위가 높은 순서대로 원소를 제거할 수 있는 추상 데이터 타입( Abstract Data Type, ADT )입니다.
- 추상 데이터 타입(Abstract Data Type, ADT)은 데이터와 그 데이터에 대한 연산들을 추상적으로 정의한 것입니다
- ADT는 데이터의 타입과 그 타입에 대해 수행할 수 있는 연산들의 집합으로 구성되지만, 이러한 연산들의 구현 방법은 정의하지 않는 것입니다.
- ADT 예시
  - 스택(Stack) ADT는 데이터의 삽입(push), 삭제(pop), 조회(peek) 등의 연산을 정의하지만, 이러한 연산들이 배열을 사용하여 구현되는지, 연결 리스트를 사용하는지 등은 명시하지 않습니다.
  - 큐(Queue) ADT는 선입선출(FIFO) 순서로 데이터를 추가하고 제거하는 연산을 정의합니다. 하지만, 이러한 연산들이 어떻게 구현되는지는 ADT의 범위를 벗어납니다.
일반적으로 힙이 우선순위 큐와 동일하다고 생각하는데 이는 사실이 아닙니다.
- 우선순위 큐는 구현방식이 없는, 즉 그냥 이론상의 개념입니다. 하지만 힙은 이제 우선순위 큐라는 개념을 실제 구현하기 위한 한 방법인 것입니다. 우선순위 큐는 힙자료구조 외에도 다양한 방법으로 구현할 수 있습니다.
- 정리하면 힙은 우선순위큐가 아니라 우선순위 큐를 구현하는 방법입니다.

힙의 정의

힙은 각 노드의 값이 해당 노드의 자식 노드의 값보다 큰(또는 작은) "완전 이진 트리"입니다.
- 힙을 사용하게 되면 최댓값과 최솟값을 O(1)만에 가져올 수 있습니다. 단, 이제 삽입이나 삭제 시에 O(logn)이 소요되게 될 것입니다. 기존에 Max나 Min을 사용하던 것을 O(n)에서 O(logn)으로 단축할 수 있습니다.
- 완전 이진 트리(complete binary tree)
  - 마지막 레벨을 제외하고, 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있습니다.
  - 완전 이진 트리 예시
  - 완전 이진 트리가 아닌 경우(마지막 레벨의 노드에 대해서 왼쪽부터 채워지지 않았습니다.)
힙인 경우와 힙이 아닌 경우
- 힙인 경우
- 힙이 아닌 경우
힙의 시간복잡도
- 삽입 : O(logN)
- 삭제 : O(logN)
- 최댓값(또는 최솟값) 추출 : O(1)

힙과 이진 탐색 트리(BST, Binary Search Tree)의 공통점과 차이점

공통점
- 힙과 BST 모두 이진 트리입니다.
차이점
- 힙은 각 노드와 값이 자식 노드보다 크거나 같습니다.(MaxHeap의 경우)
- BST의 경우 왼쪽 자식노드의 값이 가장 작고 그다음 부모노드, 그다음 오른쪽 자식 노드값이 가장 큽니다.
  - 참고로 힙의 경우 자식노드끼리에서 어떤 값이 크다는 기준은 없습니다. 먼저 들어간 값이 왼쪽부터 채워지게 됩니다.)
BST는 탐색을 위한 구조, 힙은 최대/최솟값 검색을 위한 구조라고 생각하기

힙의 분류

힙에는 Max Heap과 Min Heap이 존재합니다.
Max Heap
- 각 노드는 자식노드보다 작은 값을 갖지 않습니다.
Min Heap
- 각 노드는 자식노드보다 큰 값을 갖지 않습니다.

힙 삽입(Heap Insertion)

Max Heap에 대해서 1부터 15까지 데이터를 삽입하는 과정을 살펴보도록 하겠습니다.
- 힙은 완전 이진 트리이기 때문에 데이터 삽입시 우선 최하단 층의 리프노드를 왼쪽부터 순서대로 값을 삽입해 줍니다.
- 채워진 노드에 대해서 이제 부모노드와 비교한 뒤에, 부모노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복합니다.(Swap)

힙 삭제(Heap Delete)

Max Heap에 대해 값을 삭제하는 과정을 살펴보도록 하겠습니다.
- 최상위 값 삭제
  - 힙의 용도는 보통 최댓값 또는 최솟값을 root삭제하는 것이 일반적입니다.
  - 가장 최상단 노드를 제거한 뒤에 최하단층의 제일 오른쪽에 있는 노드를 최상단 노드로 옮겨줍니다. 그 후에 이제 자식노드들 중 더 큰 값과 swap을 진행하며 더 큰 값을 위로 올려주는 작업을 진행합니다. 값을 삭제할 때는 최상위 값을 삭제하고 다음으로 큰 값을 가져오는 과정을 진행합니다.. (힙은 각 노드가 자식노드값보다 작은 값을 갖지 않으면서 완전 이진 트리여야 합니다.)

힙 구현

코드

class MaxHeap:
    def __init__(self):
        self.heap_array = [None]  # 인덱스 0 은 무의미한 값
        self.heap_len = 0  # 실제 heap 데이터 길이 # len을 사용하면 시간복잡도 O(N)
        # 인덱스 1이 최상단 노드
        # 부모노드인덱스 = 자식노드인덱스//2
        # 왼쪽자식노드인덱스 = 부모노드인덱스**2
        # 오른쪽자식노드인덱스 = 부모노드인덱스*2+1

    def insert(self, data):
        self.heap_array.append(data)
        self.heap_len += 1

        now_idx = self.heap_len  # 최하단층 다음 인덱스
        # now_idx 가 1이면 최상단 노드임.
        # 부모노드보다 삽입값이 더 큰경우 올려주어야함
        while now_idx > 1 and self.heap_array[now_idx] > self.heap_array[now_idx // 2]:
            self.heap_array[now_idx // 2], self.heap_array[now_idx] = (
                self.heap_array[now_idx],
                self.heap_array[now_idx // 2],
            )
            now_idx = now_idx // 2

    def pop(self):
        if self.heap_len < 1:
            return None
        max_value = self.heap_array[1]

        # 제일 마지막 노드를 최상단 노드로 올리기
        self.heap_array[1] = self.heap_array[self.heap_len]
        self.heap_array.pop()
        self.heap_len -= 1

        now_idx = 1  # 최상단에 올라와있는 것을 재배치해주어야함.
        while now_idx <= self.heap_len // 2:  # 자식 노드가 존재하면 계속 내려가기
            left = now_idx * 2
            right = now_idx * 2 + 1

            if right <= self.heap_len:
                # 하나라도 크면 더 큰 값쪽으로 swap
                if (self.heap_array[now_idx] < self.heap_array[left]) or (
                    self.heap_array[now_idx] < self.heap_array[right]
                ):
                    if self.heap_array[left] > self.heap_array[right]:
                        self.heap_array[now_idx], self.heap_array[left] = (
                            self.heap_array[left],
                            self.heap_array[now_idx],
                        )
                        now_idx = left
                    else:
                        self.heap_array[now_idx], self.heap_array[right] = (
                            self.heap_array[right],
                            self.heap_array[now_idx],
                        )
                        now_idx = right
                else:  # 현재 노드가 제일 크면 break
                    break
            else:
                if self.heap_array[now_idx] < self.heap_array[left]:
                    self.heap_array[now_idx], self.heap_array[left] = (
                        self.heap_array[left],
                        self.heap_array[now_idx],
                    )
                    now_idx = left
                else:  # 현재 노드가 제일 크면 break
                    break
        return max_value

    def get_max_value(self):
        if self.heap_len >= 1:
            return self.heap_array[1]
        else:
            return None

    def get_heap_size(self):
        return self.heap_len

    def heapify_down(self, now_idx):
        while now_idx <= self.heap_len // 2:  # 자식노드가 존재할때까지
            left = now_idx * 2
            right = now_idx * 2 + 1

            if right <= self.heap_len:  # 왼쪽 오른쪽 둘다 있는 경우
                # 하나라도 크면 더 큰 값쪽으로 swap
                if (self.heap_array[now_idx] < self.heap_array[left]) or (
                    self.heap_array[now_idx] < self.heap_array[right]
                ):
                    if self.heap_array[left] > self.heap_array[right]:
                        self.heap_array[now_idx], self.heap_array[left] = (
                            self.heap_array[left],
                            self.heap_array[now_idx],
                        )
                        now_idx = left
                    else:
                        self.heap_array[now_idx], self.heap_array[right] = (
                            self.heap_array[right],
                            self.heap_array[now_idx],
                        )
                        now_idx = right
                else:  # 현재 노드가 제일 크면 break
                    break
            else:  # 오른쪽 자식노드는 없는경우
                if self.heap_array[now_idx] < self.heap_array[left]:
                    self.heap_array[now_idx], self.heap_array[left] = (
                        self.heap_array[left],
                        self.heap_array[now_idx],
                    )
                    now_idx = left
                else:  # 현재 노드가 제일 크면 break
                    break

    def heapify(self, arr):
        self.heap_array = [None] + arr
        self.heap_len = len(arr)
        # 가장 마지막 부모 노드부터 최상단 노드까지 체크진행
        for i in reversed(range(1, self.heap_len // 2 + 1)):
            self.heapify_down(i)


maxheap = MaxHeap()
maxheap.heapify([3, 1, 4, 1, 5, 9, 2, 6])
print(maxheap.heap_array)  # [None, 9, 6, 4, 1, 5, 3, 2, 1]

maxheap = MaxHeap()
maxheap.insert(1)
print(maxheap.heap_array)  # [None, 1]
maxheap.insert(2)
print(maxheap.heap_array)  # [None, 2, 1]
maxheap.insert(3)
print(maxheap.heap_array)  # [None, 3, 1, 2]
maxheap.insert(4)
print(maxheap.heap_array)  # [None, 4, 3, 2, 1]
maxheap.insert(5)
print(maxheap.heap_array)  # [None, 5, 4, 2, 1, 3]
maxheap.insert(6)
print(maxheap.heap_array)  # [None, 6, 4, 5, 1, 3, 2]
print(maxheap.pop())  # 6
print(maxheap.heap_array)  # [None, 5, 4, 2, 1, 3]
print(maxheap.pop())  # 5
print(maxheap.heap_array)  # [None, 4, 3, 2, 1]
print(maxheap.pop())  # 4
print(maxheap.heap_array)  # [None, 3, 1, 2]
print(maxheap.pop())  # 3
print(maxheap.heap_array)  # [None, 2, 1]
print(maxheap.pop())  # 2
print(maxheap.heap_array)  # [None, 1]
print(maxheap.pop())  # 1
print(maxheap.heap_array)  # [None]
print(maxheap.pop())

Python에서의 힙

heapq 라이브러리를 이용하면 손쉽게 구현이 가능합니다.

insert와 pop은 heappush, heappop으로 사용가능합니다.
기존에 구현되어 있는 리스트도 heapq.heapify를 이용한다면 최소힙구조로 변경됩니다. (만약 최대힙을 구현하고 싶다면 전체 값에 -를 붙여주면 됩니다.)

코드

import heapq

# 우선순위 큐 초기화
priority_queue = []

# 우선순위와 함께 항목을 힙에 삽입
# (우선순위, 항목) 튜플 형태로 삽입
heapq.heappush(priority_queue, (3, "apple"))
heapq.heappush(priority_queue, (1, "orange"))
heapq.heappush(priority_queue, (2, "banana"))

# 힙에서 항목을 우선순위 순서대로 제거하고 출력
while priority_queue:
    priority, item = heapq.heappop(priority_queue)
    print(f"{item} with priority {priority}")

import heapq

# 임의의 리스트
nums = [3, 1, 4, 1, 5, 9, 2, 6]

# 리스트를 힙으로 변환
heapq.heapify(nums)
print(nums) # [1, 1, 2, 3, 5, 9, 4, 6]

heapq.heappop(nums)
print(nums) # [1, 3, 2, 6, 5, 9, 4]

힙의 시간복잡도

기존 배열을 힙 배열로 변경
- python의 예시에서는 heapify로 기존 배열을 힙 배열로 변경 가능합니다.
- 시간복잡도는 O(N)입니다.
- 모든 원소에 대해서 삽입을 진행하면 O(NlogN)이어야 할 텐데 왜 O(NlogN)이 아니고 O(N)일까요?
  - O(NlogN)의 경우는 O(log1 + log2 + log3 + log4 + ... + logn) = O(NlogN)이 되는 것입니다. (앞에서부터 체크)
  - 하지만 이를 뒤에서부터 체크를 진행하면 O(N)만에 체크가 가능합니다.
    - 뒤에서부터 체크를 진행할 때는 주어진 노드의 child node들 중에서 큰 값(또는 작은 값)과 비교연산을 수행해 성질을 만족할 때까지 리프노드까지 swap을 진행합니다.
    - 이렇게 진행하게 되면 뒷부분에서 체크할 층수가 줄어 훨씬 효율적인 계산이 가능합니다.
데이터 삽입
- 시간복잡도는 O(logN)입니다.
- 부모노드부터 리프노드까지 비교를 진행하면 됩니다.
최솟값 또는 최댓값 추출
- 시간복잡도는 O(1)입니다.
- heap array에서 제일 앞에 있는 값을 인덱스를 지정해서 가져오기만 하면 됩니다.
데이터 삭제
- 시간복잡도 O(logN)
- 데이터 삭제를 진행하게 되면 힙 배열을 재배치해야 하므로 O(logN)의 시간복잡도가 소요됩니다.

힙 적용

Heap Sort(힙정렬)

Heap Sort(힙정렬)
- 힙 정렬이란 정렬을 진행하는데 Heap을 이용하여 정렬을 하는 방식입니다.
- 힙 정렬의 경우, 먼저 배열에 대해서 heap배열로 만든 뒤 (O(N)) 해당 배열에 대해서 최댓값이나 최솟값을 계속해서 뽑아내면(O(NlogN) 됩니다.
- 즉, 전체 시간 복잡도는 O(NlogN)입니다.

The Top K Problem (또는 The K-th Element)

The Top K Problem (또는 The K-th Element)
- Top K 문제란, 주어진 데이터 집합에서 가장 큰 K개의 원소 또는 가장 작은 K개의 원소를 찾는 문제입니다.
- 접근방법 1
  - 단순하게 모든 배열에 대해 Heap 배열(O(N))로 만들어주고 K개의 원소를 꺼내면(O(KlogN)) 됩니다.
  - 시간복잡도 : O(N+KlogN)
- 접근방법 2
  - 가장 큰 K개의 원소를 구하고 싶다면 K개의 데이터를 저장할 수 있는 min heap을 구성해 줍니다.
  - 그 후에 이제 K개까지 데이터를 min heap에 추가시켜 줍니다.(O(KlogK) 또는 O(K))
  - 다음 데이터에 대해서는 min heap의 최솟값과 값을 비교하면서 만약 그 최솟값보다 현재값이 크다면 해당 데이터를 min heap에 삽입시켜 줍니다.(O((N-K) logK))
  - 따라서 전체 시간복잡도는 O(NlogK)가 됩니다.
  - 이 방법은 전체 데이터 세트(N)에 비해 K가 작을 때 효율적입니다.

출처

https://leetcode.com/explore/learn/card/heap/643/heap

'Computer Science > 자료구조(Data Structure)' 카테고리의 다른 글

[자료구조] 이진 탐색 트리(BST:Binary Search Tree) (0)	2024.04.20
[자료구조] 버킷 정렬(Bucket Sort) (0)	2024.04.17
[자료구조] 기수 정렬(Radix Sort) (0)	2024.04.17
[자료구조] 계수 정렬(Counting Sort) (0)	2024.04.17
[자료구조] 퀵 정렬(Quick Sort) (0)	2024.04.17

컴돈AI

[자료구조] 힙(Heap)

힙(Heap)

우선순위 큐(Priority Queue)

힙의 정의

힙과 이진 탐색 트리(BST, Binary Search Tree)의 공통점과 차이점

힙의 분류

힙 삽입(Heap Insertion)

힙 삭제(Heap Delete)

힙 구현

Python에서의 힙

힙의 시간복잡도

힙 적용

Heap Sort(힙정렬)

The Top K Problem (또는 The K-th Element)

출처

'Computer Science > 자료구조(Data Structure)' 카테고리의 다른 글

티스토리툴바

[자료구조] 힙(Heap)

힙(Heap)

우선순위 큐(Priority Queue)

힙의 정의

힙과 이진 탐색 트리(BST, Binary Search Tree)의 공통점과 차이점

힙의 분류

힙 삽입(Heap Insertion)

힙 삭제(Heap Delete)

힙 구현

Python에서의 힙

힙의 시간복잡도

힙 적용

Heap Sort(힙정렬)

The Top K Problem (또는 The K-th Element)

출처

'Computer Science > 자료구조(Data Structure)' 카테고리의 다른 글

관련글

티스토리툴바