-
힙을 알기전
우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다.
힙이란?
-
완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
-
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
-
힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
힙의 종류
최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
key(부모 노드) >= key(자식 노드)최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
key(부모 노드) <= key(자식 노드)
힙 구현
힙을 저장하는 표준적인 자료구조는 배열 이다.
구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
최대 힙
직접 구현
import java.util.*;
public class MaxHeap {
private ArrayList<Integer> heap;
public MaxHeap() {
heap = new ArrayList<>();
}
// 최대 힙에 원소 추가
public void insert(int val) {
heap.add(val);
int index = heap.size() - 1;
heapifyUp(index);
}
// 최대 힙 유지하기 위해 위로 올라가며 정렬
private void heapifyUp(int index) {
int parentIndex = (index - 1) / 2;
while (index > 0 && heap.get(index) > heap.get(parentIndex)) {
// 부모와 자식 노드를 스왑
int temp = heap.get(index);
heap.set(index, heap.get(parentIndex));
heap.set(parentIndex, temp);
index = parentIndex;
parentIndex = (index - 1) / 2;
}
}
// 최대 힙에서 최대값 추출
public int extractMax() {
if (heap.isEmpty()) {
throw new NoSuchElementException("Heap is empty");
}
int max = heap.get(0);
int lastElement = heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heap.set(0, lastElement);
heapifyDown(0);
}
return max;
}
// 최대 힙 유지하기 위해 아래로 내려가며 정렬
private void heapifyDown(int index) {
int leftChildIndex = 2 * index + 1;
int rightChildIndex = 2 * index + 2;
int largestIndex = index;
// 왼쪽 자식과 비교
if (leftChildIndex < heap.size() && heap.get(leftChildIndex) > heap.get(largestIndex)) {
largestIndex = leftChildIndex;
}
// 오른쪽 자식과 비교
if (rightChildIndex < heap.size() && heap.get(rightChildIndex) > heap.get(largestIndex)) {
largestIndex = rightChildIndex;
}
// largestIndex가 변경되었으면 swap 후 재귀적으로 heapifyDown 호출
if (largestIndex != index) {
int temp = heap.get(index);
heap.set(index, heap.get(largestIndex));
heap.set(largestIndex, temp);
heapifyDown(largestIndex);
}
}
public static void main(String[] args) {
MaxHeap maxHeap = new MaxHeap();
maxHeap.insert(10);
maxHeap.insert(30);
maxHeap.insert(20);
maxHeap.insert(15);
maxHeap.insert(40);
System.out.println("최대값 추출: " + maxHeap.extractMax());
System.out.println("최대값 추출: " + maxHeap.extractMax());
System.out.println("최대값 추출: " + maxHeap.extractMax());
}
}
라이브러리를 통한 구현
import java.util.*;
public class MaxHeapExample {
public static void main(String[] args) {
// 내림차순 Comparator를 사용하여 최대 힙으로 PriorityQueue 생성
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// 최대 힙에 원소 추가
maxHeap.add(10);
maxHeap.add(30);
maxHeap.add(20);
maxHeap.add(15);
maxHeap.add(40);
// 최대 힙에서 최대값 추출
System.out.println("최대값 추출: " + maxHeap.poll()); // 40
System.out.println("최대값 추출: " + maxHeap.poll()); // 30
System.out.println("최대값 추출: " + maxHeap.poll()); // 20
}
}
최소 힙
직접 구현
import java.util.*;
public class MinHeap {
private ArrayList<Integer> heap;
public MinHeap() {
heap = new ArrayList<>();
}
// 최소 힙에 원소 추가
public void insert(int val) {
heap.add(val);
int index = heap.size() - 1;
heapifyUp(index);
}
// 최소 힙 유지하기 위해 위로 올라가며 정렬
private void heapifyUp(int index) {
int parentIndex = (index - 1) / 2;
while (index > 0 && heap.get(index) < heap.get(parentIndex)) {
// 부모와 자식 노드를 스왑
int temp = heap.get(index);
heap.set(index, heap.get(parentIndex));
heap.set(parentIndex, temp);
index = parentIndex;
parentIndex = (index - 1) / 2;
}
}
// 최소 힙에서 최소값 추출
public int extractMin() {
if (heap.isEmpty()) {
throw new NoSuchElementException("Heap is empty");
}
int min = heap.get(0);
int lastElement = heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heap.set(0, lastElement);
heapifyDown(0);
}
return min;
}
// 최소 힙 유지하기 위해 아래로 내려가며 정렬
private void heapifyDown(int index) {
int leftChildIndex = 2 * index + 1;
int rightChildIndex = 2 * index + 2;
int smallestIndex = index;
// 왼쪽 자식과 비교
if (leftChildIndex < heap.size() && heap.get(leftChildIndex) < heap.get(smallestIndex)) {
smallestIndex = leftChildIndex;
}
// 오른쪽 자식과 비교
if (rightChildIndex < heap.size() && heap.get(rightChildIndex) < heap.get(smallestIndex)) {
smallestIndex = rightChildIndex;
}
// smallestIndex가 변경되었으면 swap 후 재귀적으로 heapifyDown 호출
if (smallestIndex != index) {
int temp = heap.get(index);
heap.set(index, heap.get(smallestIndex));
heap.set(smallestIndex, temp);
heapifyDown(smallestIndex);
}
}
public static void main(String[] args) {
MinHeap minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(30);
minHeap.insert(20);
minHeap.insert(15);
minHeap.insert(40);
System.out.println("최소값 추출: " + minHeap.extractMin());
System.out.println("최소값 추출: " + minHeap.extractMin());
System.out.println("최소값 추출: " + minHeap.extractMin());
}
}
라이브러리를 통한 구현
import java.util.*;
public class MinHeapExample {
public static void main(String[] args) {
// 기본적으로는 최소 힙으로 PriorityQueue 생성
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 최소 힙에 원소 추가
minHeap.add(10);
minHeap.add(30);
minHeap.add(20);
minHeap.add(15);
minHeap.add(40);
// 최소 힙에서 최소값 추출
System.out.println("최소값 추출: " + minHeap.poll()); // 10
System.out.println("최소값 추출: " + minHeap.poll()); // 15
System.out.println("최소값 추출: " + minHeap.poll()); // 20
}
}
참고 사이트
끊임없이 노력하는 개발자