우선순위 큐, 최대 힙, 최소 힙

1. 우선순위 큐

우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조

특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조

2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져있음

3. 내부구조가 힙으로 구성되어 있기에 시간복잡도는 O(NLogN) 

4. 우선순위를 중요시해야하는 상황에서 주로 쓰임

선언

import java.util.PriorityQueue;
import java.util.Collections;

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

동작

///추가
pq.add(10);
pq.offer(100);

///제거
pq.poll(); //첫번째 값을 반환하고 제거, 비어있다면 null
pq.remove(); //첫번째 값 제거, 비어있다면 예외 발생
pq.peek(); //첫번째 값을 반환만 하고 제거 하지는 않음, 비어있다면 null
pq.element(); //첫번째 값을 반환만 하고 제거 하지는 않음, 비어있다면 예외 발생
pq.clear() //초기화

 

 

2. 우선순위 큐를 더 빠르게 처리할 수 있도록 만들어주는게 힙 정렬

 

2.1 완전 이진 트리

완전 이진트리(Complete Binary Tree)는 노드를 삽입할 때, 왼쪽부터 차례대로 삽입하는 트리이다.

예를들어서 좌측의 경우는 완전이진트리가 맞지만, 우측과 같은 경우는 완전 이진트리가 아니다.

2.2 최대 힙 & 최소 힙

최대힙이라고 하면 [3,4,8,10,15] 의 값이 들어왔을때 가장 위가 4일때 15가 들어오면 4를 내리고 15를 올리는 정렬이다.

추가 할때는 밑의 왼쪽부터 추가가 되고

그리고 삭제를 할때에는 가장 위에 값부터 삭제를 하고 밑의 값을 위로 하나씩 올린다.

힙의 장점은 빠르게 최대 값을 뽑아 준 뒤 다음 최대 값을 알 수 있다는 점이다.

public class MaxHeap {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        MaxPriorityQueue pq = new MaxPriorityQueue();

        int n = sc.nextInt();
        StringBuilder ans = new StringBuilder();

        while (n-- > 0) {
            int x = sc.nextInt();
            if (x == 0)
                ans.append(pq.pop()).append("\n");
            else
                pq.push(x);
        }

        System.out.println(ans);
    }

    static class MaxPriorityQueue {
        int[] heap;
        int size;


        public MaxPriorityQueue() {
            heap = new int[100000];
            size = 0;
        }

        void swap(int i, int j){
            int temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
        }

        public void push(int x) {
            heap[++size] = x;
            int current = size;

            while (current > 1) {
                int parent = current / 2;
                if (heap[parent] >= heap[current]) break;

                swap(parent, current);
                current = parent;
            }
        }

        public int pop() {
            if (size == 0) return 0;
            int ret = heap[1];

            heap[1] = heap[size--];
            int current = 1;

            while (current * 2 <= size) {
                int left = current * 2;
                int right = left + 1;
                int child = left;

                if (right <= size && heap[left] < heap[right]) {
                    child = right;
                }

                if (heap[current] >= heap[child]) break;

                swap(current, child);
                current = child;
            }

            return ret;
        }
    }
}