그동안 기초반에서 배운 것
heap, merge sort, doublely linked list

Min heap

시간복잡도가 낮다.
가장 작은게 root

Max Heap

시간복잡도가 낮다
가장 큰게 root

예제

k(=3)번째로 큰 수 찾기 -> min heap 사용
힙 사이즈 : k + 1
[28, 3, 2, 1, 2, 4, 54, 3, 5, 4, 528, 384, 92739, 8273, ...]

방법

1. k개 까지 힙에 넣기 (+ 정렬 = heapify)
2. k + 1부터 마지막 숫자까지 힙에 넣으면서 연산 수행 (아래 반복)
   2.1. 힙에 새 숫자 넣기 (힙의 맨 끝에 넣음)
   2.2. 힙 정렬 (heapify up)
   2.3. root와 맨 마지막 숫자를 swap
   2.4. 맨 마지막 숫자 pop
   2.5. 힙 정렬(heapify down)
3. root의 숫자 반환

시간복잡도

O(nlog2k) -> O(nlogk)
heapify -> O(logk)
heapify 가 up, down 두번이므로 O(logk + logk) = O(log2k)

공간복잡도

O(k+1)

코드

function buildMinHeap(arr, k) {
  if (!arr.length) return -1;
  const minHeap = new MinHeap(k + 1, arr.length);

  // build a minheap (초기 힙)
  for (let i = 0; i < k + 1; i++) {
    minHeap.insert(arr[i]);
  }

  // 힙 업데이트
  for (let i = k + 1; i < arr.length; i++) {
    minHeap.removeMin(); // swap first and last => heapfy down
    minHeap.insert(arr[i]); // put the current element in the last queue => heapify
  }

  return minHeap.removeMin();
}

다음에 배울 것

string manipulation

• sliding window
• two pointers
• rolling hash
• string matching

추후
-> trie, binary search, greedy, back tracking, recursion, memonization, monotonic queue