Heap

용도 최대 혹은 최소 원소를 효율적으로 찾을 수 있다.

Priority Queue

우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 처리되는 추상 자료형. 배열이나 연결 리스트 등으로 구현하는 방법이 있지만, 삽입 연산과 삭제 연산 중 하나는 O(1), 다른 하나는 O(N)의 시간 복잡도를 갖는다. 반면 힙으로 구현하면 삽입 연산과 삭제 연산 모두 O(logN) 시간 복잡도를 갖는다.

Heap

정의

다음 조건을 갖는 이진 트리의 한 종류
1. 완전 이진 트리여야 한다. (왼쪽 부터 채워야!)
2. 각 노드의 값은 자식 노드의 값보다 크거나 작아서는 안 됩니다.

속성

1. 삽입/삭제 연산 모두 O(logN)
2. 최대/최소 원소 찾는 연산 O(1)

분류

1. 최대 힙: 각 노드는 자식 노드보다 작지 않은 값을 가진다. 루트 노드가 최대가 된다.
2. 최소 힙: 각 노드는 자식 노드보다 크지 않은 값을 가진다. 루트 노드가 최소가 된다.

연산

1. 삽입: bottom rightmost 에 요소를 삽입하고, 힙의 정의에 맞을 때까지 부모 노드와 swap 한다.
2. 삭제: 루트 노드를 삭제하면, 그 자리에 bottom rightmost 요소를 넣어주고, 힙의 정의에 맞을 때까지 자식 노드와 swap 한다.

Java의 내장 힙

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

// Construct a Heap with initial elements. ("Heapify")
PriorityQueue<Integer> heapWithValues= new PriorityQueue<>(Arrays.asList(3, 1, 2));

minHeap.add(5);  // insertion
minHeap.peek();  // root node
minHeap.poll();  // deletion
minHeap.size();  // size

복잡도

Heap method	Time complexity	Space Complexity
Construct (Heapify)	O(N)	O(N)
Insert/Delete	O(logN)	O(1)
Get top	O(1)	O(1)
Get size	O(1)	O(1)

응용 문제

Heap Sort

보통 최대 힙으로 구현하는 편. 선택 정렬(최대값을 찾아 뒤로 옮기는 정렬)을 힙을 통해서 한다고 보면 된다. 핵심 아이디어는 (1) 정렬되지 않은 배열을 heapify (2) 힙을 사용하여 입력 배열 정렬 이다. 힙 정렬의 시간 복잡도는 O(NlogN)(최대 요소 제거에 O(logN), 최대 N-1번 수행), 공간 복잡도는 O(1)이다. 하지만 단점으로는 안정적인 정렬이 아니고, 캐시 지역성이 좋지 않아 다른 정렬들보다 성능이 떨어진다.

public class Solution {
    public void heapSort(int[] arr) {
        // Mutates elements in lst by utilizing the heap data structure
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maxHeapify(arr, arr.length, i);
        }

        for (int i = arr.length - 1; i > 0; i--) {
            // swap last element with first element
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            // note that we reduce the heap size by 1 every iteration
            maxHeapify(arr, i, 0);
        }
    }

    private void maxHeapify(int[] arr, int heapSize, int index) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int largest = index;
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }  
        if (largest != index) {
            int temp = arr[index];
            arr[index] = arr[largest];
            arr[largest] = temp;
            maxHeapify(arr, heapSize, largest);
        }
    }
}

The Top K Problem

시간 복잡도는 O(KlogN + N), 공간 복잡도는 O(N)

The K-th Element

시간 복잡도는 O(KlogN + N), 공간 복잡도는 O(N)