힙은 최댓값이나 최솟값을 빠르게 알아내기 위해 고안된 완전 이진 트리를 기본으로 한 자료구조 이다.
최소힙은 부모 노드보다 자식 노드가 큰. 즉, 부모 노드값이 더 작은 힙이고
최대힙은 부모 노드보다 자식 노드가 작은. 즉, 부모 노드값이 더 큰 힙이다.
최소힙만 알고 있으면 최대힙은 값이 반대로 들어있다고 생각하면 된다. 근본적으로 두 힙의 원리는 같다!
또한 이 힙들의 삽입,삭제에 걸리는 시간복잡도는 O(log n)으로 동일하다.
삽입과 삭제 자체만 본다면 시간복잡도는 O(1)이다.
삽입은 완전 이진 트리를 유지하기 위해 마지막 레벨의 왼쪽부터 노드를 채우면 되고
삭제는 최솟값(최댓값)을 삭제하기 때문에(Root를 제거) O(1)의 시간 복잡도를 가지지만
삽입,삭제 시 트리의 구조를 재정렬하기 위한 과정이 포함되기 때문에 최종적으로는 O(log n)의 시간 복잡도를 가진다.
간단하게 자바로 구현하기.
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());PriorityQueue(우선순위 큐)로 아주 간단하게 최소힙을 만들 수 있다. 여기서 Comparator.reverseOrder() 를 사용하면 최대힙이 된다.
