힙 (Heap)

이진 트리의 한 종류로, 이진 힙이라고도 하며, 데이터 원소들의 순서를 교묘하게 표현한 트리이다. 힙은 데이터 정렬에 이용 가능하다.

값이 최대 혹은 최소인 노드에 빠르게 접근해야 하는 응용 프로그램에 적합하다. (우선순위 큐도 힙을 사용해서 구현할 수 있다.)

• 힙 정렬 (heap sort) : 힙을 이용하여 데이터를 정렬하는 알고리즘
  
  

힙의 구조를 설계하는 방법은 두 가지가 있다. 이 두 가지는 데이터 원소의 순서 기준이 내림차순이냐 오름차순이냐에 달라지고 완전히 대칭이다.

1. 최대 힙 (max heap) : 루트 노드가 힙에서 가장 큰 값이고, 노드 각각의 값이 부모 노드의 값보다 작거나 같도록 구성된 힙
2. 최소 힙 (min heap) : 루트 노드가 힙에서 가장 작은 값이고, 노드 각각의 값이 부모 노드의 값보다 크거나 같도록 구성된 힙

힙의 3가지 성질 (제약 조건) :
1. 루트 노드는 항상 최댓값 or 최솟값이다.
2. 완전 이진 트리이다.
3. 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙 or 최소 힙이다. (재귀적)

이진 탐색 트리와의 비교 :
1. 이진 탐색 트리는 원소들은 완전한 크기 순으로 정렬되어 있다.
2. 이진 탐색 트리는 특정 키 값을 가지는 원소를 빠르게 검색할 수 있다.
3. 힙은 부가의 제약 조건이 있다.

⚠️ 힙 메모리와는 다른 개념이다!
힙 메모리 heap memory는 프로그래머가 직접 관리해야 하는 메모리의 영역을 뜻한다. 프로그래머가 작성한 코드에 따라 메모리 공간을 동적으로 할당하거나 해제하는 부분이기도 하다.
즉, 힙 데이터 구조와 아주 다른 방식으로 구현된다.

추상적 자료구조 알고리즘 구현

최대 힙을 기준으로 작성되었다.

연산 정의

• __init__() - 빈 최대 힙 생성
• insert(item) - 새로운 원소를 삽입
• remove() - 최대 원소 (root node) 반환 및 노드 삭제
  
  

빈 최대 힙 생성

insert() - 원소 삽입

remove() - 원소 삭제

힙 문제 예제

더 맵게

• import heapq
• heapq.heapify(L) : 리스트 L로부터 min heap을 구성
• heapq.heappop(L) : min heap L에서 최소값 삭제/반환
• heapq.heappush(L, x) : min heap L에 원소 x 삽입

힙을 완전 이진 트리로 구성하고, 삽입/삭제 연산을 수행

• 힙 구성 : 배열을 이용해서 구현 - O(NlogN)
• 삽입/삭제 : O(logN)
• 전체 복잡도 : O(logN)

힙 정렬은 O(NlogN)의 복잡도를 가지며, 최악의 복잡도 = 최적의 복잡도가 된다.

import heapq

def solution(scoville, K):
    # 입력 리스트를 최소 힙으로 변환
    heapq.heapify(scoville)
    count = 0

    while True:
        a = heapq.heappop(scoville)   # 힙에서 가장 낮은 스코빌 지수
        # 가장 낮은 스코빌 지수가 K 이상이면 연산 횟수 반환
        if a >= K:
            return count
        # 힙이 더 이상 원소를 포함하지 않을 경우, K를 달성할 수 없으므로 -1 반환
        if len(scoville) == 0:
            return -1

        b = heapq.heappop(scoville)   # 힙에서 다음으로 낮은 스코빌 지수
        new_scoville = a + b * 2   # 새로 계산한 스코빌 지수
        heapq.heappush(scoville, new_scoville)   # 힙에 다시 추가
        count += 1   # 수행한 연산 횟수 증가