자료구조&알고리즘
[자료구조 / 알고리즘] Heap / PriorityQueue
고쩡이
2024. 3. 19. 14:58
👩💻 힙 개념
힙 속성
- 힙은 트리 기반의 데이터 구조로, 완전 이진 트리
- 이는 주로 우선순위 큐를 구현하는데 사용.
- 힙은 큐의 선입선출 기준이 아닌, 우선순위에 따라 값을 제거. 높은 우선순위를 가진 요소가 먼저 제거된다.
- 힙은 배열을 사용하여 구현된다.
- 최대 힙과 최소 힙의 속성을 살펴본다면, 문제가 최솟값 또는 최댓값을 찾도록 요구한다면 힙이 하나의 선택지가 될 수 있다!
두 종류의 힙
- 최소 힙: 최소값이 루트 노드에 있으며, 삭제할 때 가장 작은 값이 가장 높은 우선순위를 갖는다.
- 최대 힙: 최대값이 루트 노드에 있으며, 삭제할 때 가장 큰 값이 가장 높은 우선순위를 갖는다.
힙 속성
힙으로서 이진 트리가 자격을 갖추려면 다음 속성을 충족해야 합니다:
- 구조 속성:
- 이진 힙은 완전 이진 트리여야 한다. 즉, 모든 레벨이 완전히 채워져 있으며( 가장 낮은 레벨 노드는 예외), 왼쪽에서 오른쪽으로 연속적으로 채워져야 한다.
- 순서 속성:
- 최소 힙: 모든 자손은 그 조상보다 크거나 같아야 한다.
- 최대 힙: 모든 자손은 그 조상보다 작거나 같아야 한다.
구현
이진 힙은 배열을 사용하여 구현된다.
배열은 트리를 너비 우선 탐색으로 방문한 순서대로 노드를 채우며, 인덱스 0 대신 1부터 시작한다.
완전 이진 트리의 특성을 활용하여 각 노드의 자식과 부모를 인덱스를 통해 계산할 수 있다.
leftChild = 2 * i
rightChild = 2 * i + 1
parent = i // 2
이를 통해 배열로 힙을 구현할 수 있으며, 이를 통해 노드의 위치를 파악할 수 있다. 이 과정은 트리가 완전 이진 트리일 때만 유효하다.
왜 인덱스 1부터 시작할까?
14의 왼쪽 자식과 오른쪽 자식을 찾고 싶다고 가정해 보자. 14가 인덱스 0에 있었다면 어떻게 될까? 잘 생각해 보면 0과 어떤 숫자를 곱해도 0이 되어 왼쪽 자식이 0번 인덱스에 있음을 나타내게 되는데, 이는 당연히 사실이 아니다.
Heaps Push
일반적으로 힙은 완전 이진 트리 형태를 가지므로, 새로운 요소는 트리의 가장 마지막 노드에 추가된다.
그런 다음 새로운 요소가 힙의 조건을 만족하도록 'Percolate up' 또는 'Heapify up' 과정을 거친다.
(Percolate up 과정은 새로운 요소를 힙의 올바른 위치로 이동시키는 과정이다.)
주로 최소 힙의 경우에는 새로운 요소가 부모보다 작은 값일 때, 부모와 위치를 바꾸는 작업을 반복하여 새로운 요소가 올바른 위치로 이동한다. 이 과정을 통해 힙은 항상 특정한 순서를 유지하게 되며, Push 연산을 수행한 후에도 힙의 성질이 유지된다.
PYTHON
def push(self, val):
self.heap.append(val)
i = len(self.heap) - 1 # 새로운 노드 인덱스
# Percolate up
while i > 1 and self.heap[i] < self.heap[i // 2]: # root X, 부모보다 작은값
tmp = self.heap[i] # swap
self.heap[i] = self.heap[i // 2]
self.heap[i // 2] = tmp
i = i // 2JAVA
public void push(int val) {
heap.add(val);
int i = heap.size() - 1;
// Percolate up
while (i > 1 && heap.get(i) < heap.get(i / 2)) {
int tmp = heap.get(i); // swap
heap.set(i, heap.get(i / 2));
heap.set(i / 2, tmp);
i = i / 2;
}
}
Heaps Pop
원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록한다. 그 후 힙 성질을 유지할 수 있도록 하향식으로 Heapify()를 진행한다.
PYTHON
def pop(self):
# 힙의 길이가 1이 경우, 팝할 요소가 없으므로 None 반환
if len(slef.heap) == 1:
return None
# 힙의 길이가 2인 경우, 루트노트 팝 후 해당 값 반환
if len(self.heap) == 2:
return self.heap.pop()
# 루트 노드의 값을 변수 res에 저장하여 나중에 반환하기 위해 보관
res = self.heap[1]
self.heap[1] = self.heap.pop() # 마지막 값 루트로 이동
i = 1 # 현재 노드 인덱스 포인터
# Percolate down: 노드를 아래쪽으로 이동하여 힙의 성질 유지
while 2 * i < len(self.heap): # 자식노드 O
if (2 * i + 1 < len(self.heap) and
self.heap[2 * i + 1] < self.heap[2 * i] and
self.heap[i] > self.heap[2 * i + 1]):
# 오른쪽 자식이 존재 + 왼쪽 자식 값보다 작으며 + 현재 노드 값보다 작은 경우
# (연관 2개 노드보다 작은 경우)
# 오른쪽 자식과 교체
tmp = self.heap[i]
self.heap[i] = self.heap[2 * i + 1]
self.heap[2 * i + 1] = tmp
i = 2 * i + 1 # 포인터 이동
elif self.heap[i] > self.heap[2 * i]: # 왼쪽 자식 값이 현재 노드보다 작을때
# 왼쪽 자식과 교체
tmp = self.heap[i]
self.heap[i] = self.heap[2 * i]
self.heap[2 * i] = tmp
i = 2 * i
else:
break
return resJAVA
public int pop(){
if (heap.size() == 1){return null;}
if (heap.size() == 2){return heap.remove(heap.size() - 1);}
int res = heap.get(1);
heap.set(1, heap.remove(heap.size() - 1)); // or heap.remove(1)
int i = 1;
// Percolate down
while(2 * i < heap.size()){
if ( 2*i + 1 < heap.size() &&
heap.get(2*i + 1) < heap.get(2*i) &&
heap.get(2*i + 1) < heap.get(i) ) {
// swap right child
int temp = heap.get(i);
heap.set(i, heap.get(2*i + 1));
heap.set(2*i + 1, tmp);
i = 2 * i + 1;
} else if (heap.get(2*i) < heap.get(i)) {
// swap left child
int tmp = heap.get(i);
heap.set(i, heap.get(2*i));
heap.set(2*i, tmp);
i = 2 * i;
} else {
break;
}
}
return res;
}
👀 언어별 라이브러리 모듈 알아보기
PYTHON heapq
import heapq
heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 30)
print(heap) # [10, 50, 30]
heap2 = [50, 10, 30]
heapq.heapify(heap2)
print(heap2) # [10, 50, 30]
result = heapq.heappop(heap)
print(result) # 10
"""
최대 힙 만들기
"""
heap_items = [1,3,5,7,9]
max_heap = []
for item in heap_items:
heapq.heappush(max_heap,(-item, item))
print(max_heap) # [(-9, 9), (-7, 7), (-3, 3), (-1, 1), (-5, 5)]
max_item = heapq.heappop(max_heap)[1]
print(max_item) # 9PYTHON PriorityQueue
import queue
pq = queue.PriorityQueue()
pq.put((3, 'A'))
pq.put((1, 'B'))
pq.put((2, 'C'))
while not pq.empty():
print(pq.get()) # 출력: (1, 'B'), (2, 'C'), (3, 'A')JAVA PriorityQueue
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
// 우선순위 큐 생성 (최소 힙)
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 요소 추가
pq.offer(3);
pq.offer(1);
pq.offer(2);
// 요소 확인 및 삭제 (순서에 따라 정렬되어 반환됨)
while (!pq.isEmpty()) {
System.out.println(pq.poll()); // 출력: 1, 2, 3
}
}
}public void init() throws IOException{
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
System.out.println("최소 힙");
runHeapTest(minHeap);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
System.out.println("최대 힙");
runHeapTest(maxHeap);
}
private void runHeapTest(PriorityQueue<Integer> heap) {
heap.add(1);
heap.add(8);
heap.add(5);
heap.add(2);
heap.add(3);
while(!heap.isEmpty()) {
System.out.println(heap.poll());
}
}🧐 궁금해서 찾아본 priorityQueue, heapq의 차이점
- heapq에는 heappush와 heappop 메소드가 있다. 메소드 이름이 큐 스러운 이름이 아니라서, 다른 일반 큐들과 같이 사용하기 쉽도록 priorityQueue에서는 똑같은 메소드를 put, get이라는 이름으로 제공한다.
- 그런데 heapq에 있는 메소드들이 모두 priorityQueue에서 사용할 수 있지는 않다.
- 이처럼 heapq는 특정 목적에 맞게 전문화되어있으므로, 스레드로부터 안전하지 않고, priorityQueue는 안전하다. (기본 queue 클래스를 사용하고, 이 것은 스레드를 안전하게 만들기 위한 locking을 제공)
- heapq에서 priorityQueue로 이월되지 않는 메소드들은 대체로 사용할 일이 적지만, 만약 현재 프로젝트에서 필요할 것 같으면 heapq를 사용
- 코딩 테스트의 경우에는, priorityQueue보다 heapq가 속도가 더 빠르기 때문에, heapq를 사용 권장