자료구조 - HEAP [완전이진트리, 힙, 우선순위 큐]

완전이진트리

- 루트 노드로 부터 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리이다.

즉, 마지막 깊이(level)만 제외하고 모든 레벨의 노드들이 모두 채워져있으며 될 수 있으면 왼쪽은 모두 채워 나가는 형태이다. 

 

A : 왼쪽은 완전 이진트리 이다. B: 오른쪽은 완전이진 트리가 아니다.

 

HEAP

- 완전 이진트리의 구조를 갖고 있다.

- 부모 노드가 최대 이냐 최소이냐에 따라 최대힙, 최소힙으로 나눌 수 있다.

최소 힙

최소힙 구성함수 : Min - Heapify()

- 아래에서 부모노드로 거슬러 올라가며, 부모보다 자신의 값이 더 큰 경우가 되어야한다.

- 즉, 부모보다 자신의 값이 더 작은 경우 자신과 부모노드의 자리를 바꾼다.

 

최대 힙

최대힙 구성함수 : Max - Heapify()

- 아래에서 부모노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우가 되어야한다.

- 즉, 부모보다 자신의 값이 더 큰 경우 자신과 부모노드의 자리를 바꾼다.

 

두 힙모두 

- 새로운 원소가 투입되도 이함수를 돌리면 힙성질을 유지할 수 있다.

- 함수 시간복잡도 O(logN)

 

힙 삽입

- 원소를 삽일 할때에는 가장 아래쪽에 원소가 완전 이진트리의 형태로 추가가 된다음

- 아래에서 위쪽으로 상향식으로 heapify를 수행한다.

 

힙 삭제

- 원소를 제거할 때에는 가장 위쪽의 원소가 빠지며, 가장 아래쪽의 원소가 가장 위쪽으로 옮겨간다음

- 힙성질을 만족 할때 까지 하향 식으로 Heapify를 수행한다. 

 

 

 

우선순위큐

- 우선순위대로 데이터를 정렬하면서 관리한다. (내부 구조는 힙을 이용해서 구성한다.)

- 높은 우선순위의 요소를 꺼내서 처리하는 구조

- 즉, 들어온 순서와 상관없이 가장 높은 우선순위 대로 처리된다.

- 힙을 사용하므로 우선순위를 처리하는데 일반적인 sorting보다 훨씬 빠르다. 

- 시간 복잡도 O(NlogN)

 

우선순위 큐 선언 

PriorityQueue<Object> priorityQueue = new PriorityQueue<>();

- 객체를 타입으로 받는다. 

- String 타입이나 Integer등 일반적인 타입은 arraylist.sort()와 같이 삽입과 동시에 정렬되어 유지된다.

- class 객체를 따로 만들어 쓰는 경우 ArrayList정렬과 같이 해당정렬에 Comparable<T> 혹은 Comparator<T>를 넣어 정렬해야한다.

 

add()

- 삽입에 성공한다면 true 반환

- 큐가 꽉차서 삽입에 실패한다면 IllegalStateException 예외처리

 

offer()

- 삽입에 성공한다면 true 반환

- 큐과 꽉차서 삽입에 실패한다면 false 반환

 

poll()

- 가장 우선순위가 높은 원소를 제거 하고 반환

- 비어있을시 null 반환

 

remove()

- 가장 우선순위가 높은 원소를 제거 하고 반환

- 비어있을시 NoSuchElementException 예외처리

 

 

peek()

- 가장 우선순위가 높은 원소를 참조해온다 (제거하지 않고 값만 가져온다)

- 비어있을시 null반환

 

element()

- 가장 우선순위가 높은 원소를 참조해온다 (제거하지 않고 값만 가져온다)

- 비어있을시 NoSuchElementException 예외처리

 

public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 10; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println(priorityQueue);
        for (int i = 0; i < 10; i++) {
            System.out.println(priorityQueue.poll());
        }

[1, 2, 5, 4, 3, 9, 6, 10, 7, 8]
1
2
3
4
5
6
7
8
9
10

실제 큐의 출력은 순서가 조금 다르지만 하나씩 꺼내보면 우선순위대로 정렬되어있다.

 

역정렬 우선순위 큐

 PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < 10; i++) {
            priorityQueue.add(i);
        }
        System.out.println(priorityQueue);
        for (int i = 0; i < 10; i++) {
            System.out.println(priorityQueue.poll());
        }

[9, 8, 5, 6, 7, 1, 4, 0, 3, 2]
9
8
7
6
5
4
3
2
1
0