힙(Heap)

힙이란

최대값 및 최소값을 찾아내는 연산을 하기 위한 완전이진트리를 기본으로 한 자료구조

- 완전이진트리

- 부모노드의 키 값이 자식 노드의 키 값보다 크다(최대힙) or 작다(최소힙)

노드 삽입

- 우선, 삽입하려는 노드를 완전이진트리의 맨 마지막 자리에 추가한 뒤,

부모노드와  크기를 비교해가면서 대소관계아 따라 노드를 교환하여 힙으로 다시 만드는 과정을 거친다.

노드 삭제

- 힙에서 노드의 삭제는 루트노드를 삭제하면서 반환한다는 의미이다.

최대값이나 최소값을 찾아내는 연산을 하기 위한 트리이기 때문이다.

노드에 노드가 하나도 남지 않을때까지 삭제연산을 반복해 반환된 노드들을 순서대로 늘어놓으면 오름차순 혹은 내리참순으로 정렬된 배열이 된다. 이를 힙정렬이라고한다.

루트노드와 맨마지막 노드의 자리를 바꾼다.

이렇게 맨 마지막에 오게된 루트노드는 삭제되고 반환된다.

Heap 자료구조는 Java의 Priority Queue 라는 class를 사용하면 된다.

간단한 사용법

= 초기화 =

integer를 저장하기위한 heap으로 가정하였을때,

// root로 큰값이 오는 heap

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(1, Collections.reverseOrder()); 

// root로 작은값이 오는 heap

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

기본 priority queue는 작은값이 root로 오게끔 comparator가 설정되어있다.

그래서 배치 ordering방식을 따로 정의해 주기 위해서는 개별적으로 comparator class를 작성하여 초기화 시 넣어주던지,

위와 같이 미리 작성된 comparator를 따로 지정해 주어야 한다.

= 삽입과 제거 =

// 삽입

heap.add(3);

heap.add(8);

// root값 얻기 (root 제거 X)

Integer val = heap.peek();

// root값 얻기 (root 제거 O)

Integer val = heap.poll();

출처:[Java] Heap의 구현 및 사용법