힙(Heap)이란?

[ 도입 ]

우선순위 큐

• 가장 먼저 입력된 자료가 가장 먼저 꺼내지는 큐와 달리 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다.
• 우선순위 큐의 구현으로 가장 대표적인 것이 바로 힙(heap)

---

정렬되지 않은 배열or연결리스트에서  삽입 O(1) / 삭제 O(N)

힙에서 삽입 O(logN) / 삭제 O(logN)

---

 

---

힙(Heap)이란?

• 단순히 최대 원소 or 최소 원소를 찾는 데 최적화된 형태의 완전 이진 트리이다.
  • 가장 큰(작은) 원소는 항상 트리의 루트에 들어가므로 
• 힙은 느슨한 정렬 상태를 유지한다. 
  • 부모 노드의 원소는 항상 자식 노드의 원소보다 큰(작은) 값을 가져야 한다. 
  • 대소관계는 BST와 달리 부모 자식 관계에만 적용되며 형제 노드가 갖는 원소의 크기는 제한하지 않는다.
• 중복 값을 허용한다.
• 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.
• 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.

힙 예시

 

배열을 이용한 힙의 구현

• 힙을 구현하는 자료구조는 배열이다.
• 계산의 용이성을 위해 보통 배열의 첫 번째 인덱스는 사용하지 않는다.
• A[ i ]에 대응되는 노드의 왼쪽 자식은 A[ 2i ]에 대응된다.
• A[ i ]에 대응되는 노드의 오른쪽 자식은 A[ 2i + 1]에 대응된다.

배열로 구현된 힙

 

 

힙의 삽입

1. 새 노드는 항상 힙의 맨 끝에 추가된다.
2. 자신의 부모 노드의 값을 비교해서 부모 노드의 값이 자신 보다 작다면 위치를 바꾼다.
3. 새 노드가 더 크거나 같은 값을 가진 부모 노드를 만나거나, 루트에 도달할 때까지 반복한다.

삽입할 27을 맨 끝 노드에 추가

27은 12보다 크므로 교환

27은 25보다 크므로 교환, 32보다 작으므로 중지

 

힙의 삭제

1. 힙에서 삭제되어야 하는 원소는 루트이다.
2. 힙의 마지막 노드를 루트에 덮어 씌운다.
3. 힙의 대소 관계 조건을 만족시킨다.

맨 마지막 노드 3을 루트로

더 큰 25와 교환

더 큰 15와 교환

 

---

문제1) 힙(Heap)  >  더 맵게

힙 문제이나 아무 생각 없이 짠 코드

정확성 테스트는 다 통과했지만 효율성 테스트 0점

def solution(scoville, K):
    answer = 0
    
    while True:
        scoville.sort()
        
        if scoville[0] >= K:
            break
        elif len(scoville) == 1:
            answer = -1
            break
        
        scoville.append(scoville[0] + (scoville[1]*2))
        scoville = scoville[2:]
        
        answer += 1
    return answer
 
 

최소 원소를 빠르게 꺼낼 수 있어야 한다  =>  힙(Heap)의 필요성!

---

Python: import heapq

C++ : priority_queue<T, Container, Compare>

Java: PriorityQueue 클래스 이용

---

모범 답안

import heapq
 
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while True: 
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            break
        elif len(scoville) == 0:
            answer = -1
            break
        
        min2 = heapq.heappop(scoville)
        new_scoville = min1 + 2*min2
        heapq.heappush(scoville, new_scoville)
        answer += 1
        
    return answer

모범 답안에서의 복잡도 : O(nlogn) 

 

추천 문제1) 백준 11286번 절대값 힙

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

처음 풀이에서 계속 시간 초과가 났는데  input을 sys.stdin.readline으로 입력 형태만 바꾸니 통과했다.

찾아보니 많은 수의 입력을 받을 때 input 대신 오른쪽 같이 사용하면 시간을 줄일 수 있다고 한다.

시간 초과 풀이 vs 통과한 풀이

 

추천 문제2) 백준 1655번 가운데를 말해요

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

힙 문제인데 풀이 생각해내는게 굉장히 어려웠다. 한 번 풀어보는 것을 추천!

 

 

References

알고리즘 문제해결 전략2
힙(자료구조) - 위키백과