Chapter 16. 힙으로 우선순위 유지하기

♧ Self-study/<누구나 자료구조와 알고리즘>

Chapter 16. 힙으로 우선순위 유지하기

Grit_0913 2024. 9. 19. 19:32

Chapter 16. 힙으로 우선순위 유지하기

하단의 목차를 클릭하여 이동할 수 있습니다 :)

1. 우선순위 큐
2. 힙
3. 힙 속성 (최대 힙)
3-1. 삽입
3-2. 삭제
3-3. 힙 vs 정렬된 배열
4. 마지막 노드 문제
4-1. 배열 기반 힙 순회
4-2. 힙 삽입 코드
4-3. 힙 삭제 코드
5. 우선순위 큐로 쓰이는 힙
6. 연습 문제 정리
6-1. 3 번 (힙 정렬)

힙은 데이터 세트에서 가장 큰 또는 가장 작은 데이터 원소를 계속 알아내야 할 때 특히 유용하다.

1. 우선순위 큐

우선순위 큐(priority queue)의 삭제와 접근은 전형적인 큐와 유사하다. 그러나 삽입은 정렬된 배열과 유사한 리스트이다.
- 삭제 & 접근 : 우선순위 큐 앞에서만 수행된다 (FIFO).
- 삽입 : 항상 데이터가 특정 순서대로 정렬되도록 조정한다.
병원 응급실 예
- 병원의 응급실은 환자의 중증도에 따라 진료 순서가 정렬된다. 따라서 새로운 환자가 접수 되었을 때(삽입) 해당 환자의 중증도에 따라 진료 순서가 정렬된다.
우선순위 큐는 추상 데이터 타입이다.
일반적으로 우선순위 큐를 구현할 때 자료 구조로 힙을 사용한다. (정렬된 배열을 이용할 수도 있긴하다).
- 배열 기반 우선순위 큐는 삭제가 $O(1)$, 삽입이 $O(N)$ 이다. 힙은 배열보다 더 나은 시간 복잡도를 갖는다.

2. 힙

교재에서 다루는 힙은 이진 힙(binary heap)이다.
이진 힙은 특수한 종류의 이진 트리이다. 이진 힙에는 최대 힙(max-heap)과 최소 힙(min-heap) 두 가지가 존재한다.
- 최대 힙 (max-heap)
  - 힙 조건 (heap condition)
    - 각 노드의 값은 해당 노드의 모든 자손 노드들의 값보다 크다.
    - 힙 조건으로 인해 이진 탐색 트리는 절대 힙이 될 수 없다. (노드의 정렬문제 때문).
  - 트리는 완전(complete)해야 한다.
    - 완전 트리(complete tree)란 트리에 빠진 노드가 없는 트리를 의미한다.
      - 단, 마지막 레벨에서는 빠진 노드가 존재할 수 있다.
      - 빠진 노드가 존재할 경우 무조건 왼쪽부터 노드가 채워져 있어야 한다.
- 최소 힙(min-hea)
  - 힙 조건
    - 각 노드의 값은 해당 노드의 모든 자손 노드들의 값보다 작다.
  - 트리는 완전(complete)해야 한다.

3. 힙 속성 (최대 힙)

힙은 이진 탐색 트리에 비해 약한 정렬(weakly ordered) 이다.
- 힙은 자손이 조상보다 크지 않다는 분명한 순서만 존재할 뿐 내부의 정렬 상태는 알 수 없다.
힙은 약한 정렬이기에 검색이 불가하다.
힙의 루트 노드는 항상 최댓 값이다. (힙의 자손이 조상보다 클 수 없기 때문이다).
마지막 노드(last node)
- 힙의 마지막 노드는 바닥 레벨에서 가장 오른쪽에 있는 노드이다.

3-1. 삽입

삽입 수행
- step 1 : 삽입할 노드를 생성한다.
- step 2 : 삽입할 노드를 마지막 노드 우측에 삽입한다.
  - 삽이된 노드가 마지막 노드가 된다.
- step 3 : 새로 삽입된 노드와 삽입된 노드의 부모 노드와 크기를 비교한다.
  - 새 노드 > 부모 노드 : 새 노드와 부모 노드를 스왑한다.
- step 4 : '새 노드 < 부모 노드'를 만족할 때까지 'step 1 ~ step 3'을 반복한다.
삽입을 수행하면 삽입된 노드는 '새 노드 < 부모 노드'를 만족할 때까지 트리의 위로 올라간다. 이를 노드를 위로 '트리클링 trickling)한다고 표현한다.
힙 삽입의 빅 오는 $O(logN)$ 이다.
- $N$ 개의 노드를 갖는 트리는 약 $logN$의 레벨을 갖는다.
- 최대 레벨($logN$)의 수만큼 트리크링 할 수 있다.

3-2. 삭제

힙은 루트 노드만 삭제할 수 있다. (큐와 동일).
- 검색이 불가하기 때문이다.
삭제 수행
- step 1 : 마지막 노드를 루트 노드 자리로 옮긴다. (기존 루트 노드 삭제).
- step 2 : 루트 노드(옮겨진 마지막 노드)가 자기 자리를 찾아갈 수 있도록 아래로 트리클랑힌다.
  - step 1 : 트리클 노드의 두 자식 중 어느 쪽이 더 큰지 확인한다.
  - step 2 : 트리클 노드가 큰 자식보다 작으면 큰 자식과 트리클 노드를 스왑한다.
  - step 3 : 트리클 노드보다 큰 자식이 없을 때 까지 'step 1 ~ step 2' 를 반복한다.
힙 삭제의 시간 복잡도는 $O(logN)$ 이다. (소수점이 있는 실수일 경우 +1이 된다, e.g. 9.xx → 10).
- N 개의 노드를 갖는 트리의 레벨이 약 $logN$이기 때문이다.

3-3. 힙 vs 정렬된 배열

정렬된 배열 대신 힙을 사용하는 이유는 다음과 같다. 요약하면 삭제의 경우 배열이 더 효율적이지만 그 차이가 힙과 크게 차이가 나지 않기 때문이다.
- 삽입 : 배열은 $O(N)$, 힙은 $O(logN)$으로 힙이 더 효율적이다. 이는 $N$이 커질수록 그 차이가 크게 차이가 난다.
- 삭제 : 배열은 $O(1)$, 힙은 $O(logN)$으로 배열이 더 효율적이다. 그러나 실상 $O(1)$과 $O(logN)$의 차이는 그렇게 크지 않다.

4. 마지막 노드 문제

힙은 항상 마지막 노드를 기준으로 작업을 수행한다. 그 이뉴는 균형 트리를 유지하기 위해서이다.
- 균형 트리를 유지해야만 힙의 시간 복잡도가 $O(logN)$이 되기 때문이다.
힙은 마지막 노드를 찾기 위해 주로 배열을 사용해 구현된다. 즉, 힙은 배열을 내부적 자료 구조로 하는 추상 데이터 타입이다.
- 루트 노드는 항상 index 0 이다.
- 첫 레벨부터 끝 레벨까지 레벨별로 왼쪽부터 index가 부여된다.
위처럼 배열을 통해 힙을 구현하면 항상 배열의 마지막 원소가 마지막 노드가 된다. 따라서 배열의 마지막 원소에 접근하여 작접을 수행할 수 있다.
코드 구현

class Heap:
    def __init__(self):
        self.data = []

    def root_node(self):
        if self.data:
            return self.data[0]
        else:
            return None

    def last_node(self):
        if self.data:
            return self.data[-1]
        else:
            return None

4-1. 배열 기반 힙 순회

배열을 기반으로한 힙의 인덱스를 활용하면 다음 공식을 만족한다.
- 특정 노드의 왼쪽 자식 = $(index \times 2) + 1$
- 특정 노드의 오른쪽 자식 = $(index \times 2) + 2$
- 특정 노드의 부모 노드 = ${(index - 1)}\over2$
  - 정수 나누셈을 활용하기에 소수점 아래를 '버림'한다.
코드 구현

class Heap:
    def __init__(self):
        self.data = []

    def root_node(self):
        if self.data:
            return self.data[0]
        else:
            return None

    def last_node(self):
        if self.data:
            return self.data[-1]
        else:
            return None
            
# 인덱스 규칙 구현------------------------------------------   
    # 왼쪽 자식 찾기
    def left_child_index(self, index):
        return (index * 2) + 1
    
    # 오른쪽 자식 찾기
    def right_child_index(self, index):
        return (index * 2) + 2
    
    # 부모 노드 찾기
    def parent_index(self, index):
        return (index - 1) / 2

4-2. 힙 삽입 코드

class Heap:
    def __init__(self):
        self.data = []

    def root_node(self):
        if self.data:
            return self.data[0]
        else:
            return None

    def last_node(self):
        if self.data:
            return self.data[-1]
        else:
            return None
            
# 인덱스 규칙 구현------------------------------------------   
    # 왼쪽 자식 찾기
    def left_child_index(self, index):
        return (index * 2) + 1
    
    # 오른쪽 자식 찾기
    def right_child_index(self, index):
        return (index * 2) + 2
    
    # 부모 노드 찾기
    def parent_index(self, index):
        return (index - 1) / 2
        
# 힙 삽입---------------------------------------------------
    def insert(self, value):
        # value를 배열 끝에 삽입해 마지막 노드로 만든다.
        self.data.append(value)
        
        # 새로 삽입한 노드의 인덱스를 저장한다.
        new_node_index = len(self.data) - 1
        
        # 다음 루프는 "위로 트리클링"하는 알고리즘을 실행한다.
        while new_node_index > 0 and self.data[new_node_index] > self.data[self.parent_index(new_node_index)]:
            # 새 노드와 부모 노드를 스왑한다.
            parent_idx = self.parent_index(new_node_index)
            self.data[parent_idx], self.data[new_node_index] = self.data[new_node_index], self.data[parent_idx]
            
            # 새 노드의 인덱스를 업데이트한다.
            # 실제 배열의 인덱스가 변하지는 않지만
            # while loop이 반복되는 동안 제자리를 찾아가기 위해
            # 반복 조건으로 new_node_index를 계속 업데이트 한다.
            new_node_index = parent_idx

4-3. 힙 삭제 코드

class Heap:
    def __init__(self):
        self.data = []

    def root_node(self):
        if self.data:
            return self.data[0]
        else:
            return None

    def last_node(self):
        if self.data:
            return self.data[-1]
        else:
            return None
            
# 인덱스 규칙 구현--------------------------------------------------- 
    # 왼쪽 자식 찾기
    def left_child_index(self, index):
        return (index * 2) + 1
    
    # 오른쪽 자식 찾기
    def right_child_index(self, index):
        return (index * 2) + 2
    
    # 부모 노드 찾기
    def parent_index(self, index):
        return (index - 1) / 2
        
# 힙 삽입------------------------------------------------------------
    def insert(self, value):
        # value를 배열 끝에 삽입해 마지막 노드로 만든다.
        self.data.append(value)
        
        # 새로 삽입한 노드의 인덱스를 저장한다.
        new_node_index = len(self.data) - 1
        
        # 다음 루프는 "위로 트리클링"하는 알고리즘을 실행한다.
        while new_node_index > 0 and self.data[new_node_index] > self.data[self.parent_index(new_node_index)]:
            # 새 노드와 부모 노드를 스왑한다.
            parent_idx = self.parent_index(new_node_index)
            self.data[parent_idx], self.data[new_node_index] = self.data[new_node_index], self.data[parent_idx]
            
            # 새 노드의 인덱스를 업데이트한다.
            # 실제 배열의 인덱스가 변하지는 않지만
            # while loop이 반복되는 동안 제자리를 찾아가기 위해
            # 반복 조건으로 new_node_index를 계속 업데이트 한다.
            new_node_index = parent_idx
            
# 힙 삭제-----------------------------------------------------------
    def delete(self):
        # 힙에서는 루트 노드만 삭제하므로
        # 배열에서 마지막 노드를 팝해 루트 노드로 넣는다.
        self.data[0] = self.data.pop()
        
        # "트리클 노드"의 현재 인덱스를 기록한다.
        trickle_node_index = 0

        # 다음 루프는 "아래로 트리클링"하는 알고리즘을 실행한다.
        # 트리클 노드에 자기보다 큰 자식이 있으면 루프를 실행한다.
        while self.has_greater_child(trickle_node_index):
            # 더 큰 자식의 인덱스를 변수에 저장한다.
            larger_child_index = self.calculate_larger_child_index(trickle_node_index)

            # 트리클 노드와 더 큰 자식을 스왑한다.
            self.data[trickle_node_index], self.data[larger_child_index] = \
            self.data[larger_child_index], self.data[trickle_node_index]

            # 트리클 노드의 새 인덱스를 업데이트한다.
            trickle_node_index = larger_child_index

    def has_greater_child(self, index):
        # index에 있는 노드에 왼쪽 자식이나 오른쪽 자식이 있는지
        # 어느 한 자식이라도 index에 있는 노드보다 큰지 확인한다.
        left_index = self.left_child_index(index)
        right_index = self.right_child_index(index)
        return (left_index < len(self.data) and self.data[left_index] > self.data[index]) or \
               (right_index < len(self.data) and self.data[right_index] > self.data[index])

    def calculate_larger_child_index(self, index):
        left_index = self.left_child_index(index)
        right_index = self.right_child_index(index)

        # 오른쪽 자식이 없으면
        if right_index >= len(self.data):
            # 왼쪽 자식의 인덱스를 반환한다.
            return left_index

        # 오른쪽 자식의 값이 왼쪽 자식의 값보다 크면
        if self.data[right_index] > self.data[left_index]:
            # 오른쪽 자식의 인덱스를 반환한다.
            return right_index
        else:
            # 왼쪽 자식의 인덱스를 반환한다.
            return left_index

5. 우선순위 큐로 쓰이는 힙

우선순위 큐의 주요 함수는 큐에서 가장 높은 우선순위를 갖는 항목에 바로 접근하는 것이다.
- 힙은 우선순위 큐에 가장 적합하다. 힙은 가장 높은 우선순위의 항목을 항상 루트 노드에 갖고 있기 때문이다.
힙은 루트 노드를 처리할 때 다음 우선 순위 노드를 루트 노드로 가져오는 특징이 있다. 또한 삽입과 삭제 모두 $O(logN)$으로 매우 빠르다.
- 반면 정렬은 삽입에 $O(N)$이 걸리므로 매우 느리다.
결론적으로 힙은 약한 정렬로인해 검색은 불가하지만 삽입과 삭제에 있어 매우 효율적이다.

6. 연습 문제 정리

6-1. 3 번 (힙 정렬)

위 그림은 55, 22, 34, 10, 2, 99, 68을 순서대로 힙에 삽입했을 때 완성되는 트리이다.
- 즉 루트 노드에 삽입하고 트리클링을 반복한 결과이다.
위의 힙(트리)에서 루트 노드를 삭제하고 새로운 힙에 삽입을 한다.
- 하나의 힙에서 삭제를 하고 해당 노드를 다시 새로운 힙에 삽입을 반복하면 힙 정렬(Heapsort)이 수행된다.
  - 최대 힙은 오른차순으로 정렬된다.
  - 최소 힙은 내림차순으로 정렬된다.

답

직접 3 번 문제를 풀어보면 위와 같은 결과가 나온다.

'♧ Self-study > <누구나 자료구조와 알고리즘>' 카테고리의 다른 글

Chapter 18. 그래프로 뭐든지 연결하기 (0)	2024.09.22
Chapter 17. 트라이(trie)해 보는 것도 나쁘지 않다 (0)	2024.09.20
Chapter 15. 이진 탐색 트리로 속도 향상 (2)	2024.09.17
Chapter 14. 노드 기반 자료 구조 (0)	2024.09.14
Chapter 13. 속도를 높이는 재귀 알고리즘 (9)	2024.09.11

현재글Chapter 16. 힙으로 우선순위 유지하기

Grit

Grit 입니다.

like, where, 자료 구조 알고리즘 (ds & algo), SUM, CASE WHEN, Having, 태블로 (Tableau), split(), 머신러닝 (machine learning), 프로그래머스 알고리즘, R, date_format, Round, SELF JOIN, AVG, date, SQL 코딩테스트, 회귀분석 (regression), 경영정보시각화, 알고리즘, subquery, TIMESTAMPDIFF, Limit, year, count, 통계 검정 (statistical test), order by, GROUP BY, INNER JOIN, concat,

Today :
Yesterday :

Grit

Chapter 16. 힙으로 우선순위 유지하기

Chapter 16. 힙으로 우선순위 유지하기

1. 우선순위 큐

2. 힙

3. 힙 속성 (최대 힙)

4. 마지막 노드 문제

5. 우선순위 큐로 쓰이는 힙

6. 연습 문제 정리

'♧ Self-study > <누구나 자료구조와 알고리즘>' 카테고리의 다른 글

'♧ Self-study/<누구나 자료구조와 알고리즘>'의 다른글

티스토리툴바

« 2025/04 »
일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

Chapter 16. 힙으로 우선순위 유지하기

Chapter 16. 힙으로 우선순위 유지하기

1. 우선순위 큐

2. 힙

3. 힙 속성 (최대 힙)

4. 마지막 노드 문제

5. 우선순위 큐로 쓰이는 힙

6. 연습 문제 정리

'♧ Self-study > <누구나 자료구조와 알고리즘>' 카테고리의 다른 글

'♧ Self-study/<누구나 자료구조와 알고리즘>'의 다른글

관련글

티스토리툴바