[CS] 힙(Heap)

giggle·2023년 8월 23일

📌 힙(Heap)이란?

이진 트리를 기반으로 한 자료구조로서, 힙은 최댓값이나 최솟값을 빠르게 찾아내기 위해 고안되었습니다. 힙은 보통 우선순위 큐(Priority Queue)를 구현하기 위해 사용되며, 힙의 주요 특징은 부모 노드와 자식 노드 간의 관계를 통해 정의됩니다.

종류

최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

예시

시뮬레이션 시스템
네트워크 트래픽 제어
운영 체제에서의 작업 스케쥴링
수치 해석적인 계산

📌 구현

왼쪽 자식 index = (부모 index) * 2
오른쪽 자식 index = (부모 index) * 2 + 1
부모 index = (자식 index) / 2

삽입

힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입합니다.
새로운 노드를 부모 노드들과 교환합니다.

삭제

최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제됩니다. (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것)
삭제된 루트 노드에는 힙의 마지막 노드를 가져옵니다.
힙을 재구성합니다.

📌 우선순위 큐(Priority Queue)

Priority Queue는 Queue와 구조가 비슷합니다. Queue는 FIFO(First In First Out)구조로 먼저들어온 순서대로 데이터가 나가게 되지만 Priority Queue란 데이터의 우선순위를 정해 우선순위가 높은 순서대로 나가게됩니다.

우선순위 큐는 우선순위 힙으로 구현을 할 수 있습니다.

데이터를 삽입할 때 우선순위의 최대, 최소를 구성하여 데이터가 빠지면 중간을 계속해서 채워넣는 방식입니다.

선언방식

// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();

// Integer 타입으로 우선순위 큐 선언(높은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(Collections.reverseOrder());		
		
// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQueue3 = new PriorityQueue<>();

// Integer 타입으로 우선순위 큐 선언(높은 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQueue4 = new PriorityQueue<>(Collections.reverseOrder());

사용

PriorityQueue<Integer> pq = new PriorityQueue<>();

// 데이터 추가
pq.add(1);
pq.add(2);
pq.add(3);

// 데이터 삭제
pq.poll();
pq.remove(1);

// 순차 출력
Iterator iterator = pq.iterator();
while(iterator.hasNext())
	System.out.print(iterator.next() + " ");

// 초기화
pq.clear();