기억하자!
- 힙은 우선순위 큐이다.
- 힙은 로그함수를 따른다.
우선순위 큐 , 힙
우선순위 큐란, 각 데이터에 우선순위가 있는 자료구조를 정의하는 추상 데이터 타입이다.
즉, 데이터가 우선순위를 가지고 있기 때문에 우선순위에 따라 요소를 꺼낼 수 있다.
우선순위를 구현한 구체적인 데이터 타입이 힙이다.
📌 힙이란
힙은 트리 기반의 자료구조로, 각 노드는 값(키)과 우선순위를 가진다.
힙은 우선순위를 연산할 수 있어야 하기 때문에 정수나 문자처럼 연산할 수 있어야한다.
또한 부모와 자식 노드간의 관계는 정의되어있지만, 그 외 사촌이나 형제 관계에 대해서는 우선순위가 없다.
이진 힙은 그 중에서도 이진 트리를 사용해 만든 힙이다.
이진 트리란, 각 노드의 자식 노드가 반드시 3개이하인 트리를 말한다.
이진 힙
이진 힙은 이진 트리를 사용해서 만든 힙이다.
최대 힙
부모 노드의 우선순위가 항상 자식 노드의 우선순위보다 크거나 같고, 우선순위가 가장 높은 노드는 루트이다. 즉 값이 가장 크다.
📌 최소 힙
부모 노드의 우선순위가 항상 자식 노드의 우선순위보다 작거나 같고, 우선순위가 가장 낮은 노드가 루트 누드이다.
힙을 사용하는 적절한 상황
최대 힙에서 최댓값을 찾거나 최솟값을 찾는 대에는 상수시간을 따른다.
그러나 제거를 해야하는 상황에서는 삭제 후 재정렬이 필요하기 때문에 로그함수를 따른다.
힙에 데이터를 삽입하는 작업 역시 로그 함수를 따른다.
탐색 작업은 선형시간을 따른다.
따라서 힙은 우선순위에 따라 실행해야 하는 작업에 적합하다.
-
운영체제는 힙을 사용해서 여러 작업을 관리하고, 각 작업의 우선순위에 따라 지원을 할당하도록 설계한다.
-
또한 그래프에서 두 노드의 최단 경로를 찾는 데이크스트라 알고리즘을 구현할 때에도 사용한다.
-
당연히 립 정렬에도 사용된다.
이진 힙 구현 개념(힙 구조화 하기)
힙 구조화란?
배열과 같은 자료구조에서 이진 힙을 만드는 것을 말한다.
즉, 직접 트리를 구현하지 않아도 부모-자식간의 인덱스 관계를 활용해서 이진 힙 관계를 만들 수 있다.
힙을 리스트에 저장할 때, 인덱스 구하기
K 인덱스의 자식 노드는 2K+1이고, 오른쪽 자식 노드는 2K+2이다.
파이썬의 힙큐
파이썬의 내부 모듈인 heapq은 최소힙을 만들어주는 알고리즘을 제공한다.
📌 최소 힙
부모 노드의 우선순위가 항상 자식 노드의 우선순위보다 작거나 같고, 우선순위가 가장 낮은 노드가 루트 누드이다.내부 모듈인 heapq의 함수
heapq.heapify(리스트): 리스트를 정렬된 최소힙의 형태 heap으로 만들어준다.heapq.heappush(힙,item):item을 heap에 추가해준다.heapq.heappop(heap): 가장 작은 원소를 꺼내고, 남은 키를 재정렬한다.비어 있는 경우 IndexError가 호출됨.
만약 최소힙이 아닌 최대힙이 필요한 상황이라면?
- 정수의 경우 : 각 값에
-1을 곱한다.
예제 - 최소 비용 로프 연결하기
문제
길이가 다른 로프 리스트가 주어진다. 이들을 모두 연결하면서 전체 비용이 가장 낮은 순서를 찾아야한다.
두 로프를 연결하는 비용은 두 로프의 합이고, 전체 비용은 전체 로프를 연결하는데 드는 비용의 합이다.
입력 : [5,4,3,8]
출력 : 36
🚩 핵심 아이디어
가장 작은 로프들부터 연결해야한다 -> 가장 먼저 연결한 로프의 경우, 가장 많이 최종 합에 반복적으로 더해지기 때문이다.
따라서 최종 합을 줄이려면 큰 값이 최대한 덜 더해져야한다.
구현코드
from heapq import heapify,heappop,heappush
rope_heap = [1,3,5,7]
heapify(rope_heap)
total_cost = 0
while len(rope_heap) > 1:
temp_cost = heappop(rope_heap) + heappop(rope_heap)
total_cost += temp_cost
heappush(rope_heap,temp_cost)
print(total_cost)