자료구조) Tree - Heap, Priority Queue (힙, 우선순위 큐)

Heap (힙)

• Max Heap / Min Heap
• Parent Node가 Child Node보다 항상 크거나(작거나) 같은 Complete Binary Tree (완전이진트리)
• (자식노드끼리는 상관없음)
• (항상 root가 max/min이므로 최대-최소값을 찾기 편하다)
• 시간 복잡도 : O(logn) (힙의 삽입-삭제는 최악의 경우, 최하단노드~최상단노드까지 swap이 필요하다)

• 삽입&삭제 시에도 '완전이진트리'형태를 유지해야한다.
• 삽입 : 마지막 노드의 다음자리를 확장하고 임시로 저장후, 부모노드와 비교해가며 swap한다.
• 삭제 : 항상 root를 삭제해 반환한다. 마지막 노드를 root자리에 임시로 저장후 삭제하고, root에 있는 값을 자식들과 비교해가며 적당한 자리까지 swap한다.

Heap을 이용한 오름차순 정렬

Input	Output
첫 번째 줄에 정렬할 원소의 수 N, 두 번째 줄에는 정렬해야 할 원소 n개가 입력된다.	정렬 후의 원소들을 출력한다.

import java.util.*;

public class Test {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        ArrayList<Integer> heap = new ArrayList<>();
        ArrayList<Integer> sort = new ArrayList<>();

        heap.add(0); // for 1-based tree. 0번째는 쓰지않음

        for (int i = 1; i <= n; i++) { // heap형태로 받아들인다. 'heap추가' 로직 이용
            heap.add(scanner.nextInt());
            for (int j = i; j > 1; j /= 2) {
                if (heap.get(j) < heap.get(j / 2)) {
                    int temp = heap.get(j); // swap
                    heap.set(j, heap.get(j / 2));
                    heap.set(j / 2, temp);
                }
            }
        }

        for(int i=1; i<=n; i++) // heap형태 확인가능
            System.out.print(heap.get(i)+" ");
        System.out.println();

        for (int i = 1; i <= n; i++) { // 오름차순 정렬. 'heap삭제' 로직 이용
            sort.add(heap.get(1));
            heap.set(1, heap.get(n - i + 1));
            for (int j = 1; ; ) {
                int k = j * 2;
                if (k > n - i) break;
                if (k + 1 <= n - i && heap.get(k) > heap.get(k + 1)) k++;
                if (heap.get(j) > heap.get(k)) {
                    int temp = heap.get(j);
                    heap.set(j, heap.get(k));
                    heap.set(k, temp);
                    j = k;
                }
                else break;
            }
        }

        for (int i = 0; i < n; i++)
            System.out.print(sort.get(i) + " ");

    }
}

// 'Binary Tree' 글의 순차자료구조 표를 참고하자 (부모노드는 i/2)
// Heap 추가-삭제 로직을 이용해 heap및sort 구성하였음

---

Priority Queue (우선순위 큐)

이름과 달리, 하는 일과 내부구조가 Queue와는 아예 다른 자료구조
top, pop을 통해 추출되는 원소가 제일먼저 들어온 값이 아닌 현재 큐안에서 우선순위가 가장 높은 값이다.

List가 연결리스트나 배열로 구현되는것처럼
Priority Queue도 List, Map처럼 추상적인 개념이지만
일반적으로 Priority Queue = Heap으로 동의어처럼 쓰인다.