Heap

힙 종류에는 Max- heap, min- heap이 있다.

힙은 완전 이진 트리 구조임.

이 자료구조를 이용하면 특정 수가 추가되고 삭제되었을 때 원하는 heap 구조를 유지하는 데 O(logN) 만큼이 소요되며, 이는 주어진 수들 중 최대 최소 값을 O(1)에 구할 수 있도록 만들어준다.

max-heap을 예로 들면 max-heap에서의 삭제는 루트 노드에서만 가능하다.

max-heap을 이용하면 삽입, 삭제에 O(logn)만큼의 시간만 소요하여 그 다음 최댓값을 루트에 올린다.

따라서 max-heap에서는 k 번째 최댓값은 구할 수 가 없다.