99클럽 코테 스터디 28일차 TIL + Heap(2)

학습 키워드

- Heap

 

공부한 내용

힙은 최소 힙(Min Heap), 최대 힙(Max Heap) 두가지가 있다.

• 최소 힙은 루트노드가 최솟값이 되고, 부모노드의 key는 자식노드의 Key보다 작아야 한다는 규칙이 있다.
• 최대 힙은 루트노드가 최댓값이 되고, 부모노드의 Key가 자식 노드의 Key보다 커야 한다는 규칙이 있다.

최소 힙(Min Heap)

• 최소 힙(Min Heap)은 부모 노드의 Key가 자식 노드의 Key보다 작거나 같은 완전 이진 트리이다.
• 단지 부모 노드가 자식 노드의 Key보다 작기만 하면 된다.
• 자바에서 최소 힙을 사용하는 것은 Primary Queue를 그대로 사용해주면 된다.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

• Primary Queue는 우선순위 큐로 우선순위가 가장 낮은 값이 먼저 나오게 되어 있다. 우선순위가 낮다는 것은 Integer를 넣었을 때, 최소값으로 판단되므로 이렇게 구현할 수 있다.

최소 힙의 삽입 과정

• 트리의 가장 끝 위치에 데이터를 삽입하고, 부모 노드와 key 값을 비교하여 작은 경우 부모 노드와 자리를 교체하는 것을 반복한다.

최소 힙의 삭제 과정

• 힙은 삭제할 때 최상위 노드를 반환하며 삭제한다. 마치 Queue 의 poll()과 같다.
• 최상위 노드를 삭제한 후 최상위 노드에 가장 가까운 마지막 위치의 노드를 위치시킨다.
• 그 후, 삽입과 반대의 과정으로 자식노드와 비교하며 자리를 교체한다.

(좌, 우 노드와 비교하여 더 작은 값과 자리를 교체한다.)

최대 힙(Max Heap)

• 최대 힙(Max Heap)은 부모 노드의 Key가 자식 노드의 Key보다 크거나 같은 완전 이진 트리이다.
• 단지 부모 노드가 자식 노드의 Key보다 크기만 하면 된다.
• 최대 힙을 사용하는 방법은 Comparator 값을 세팅해주어 사용할 수 있다.

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return - Integer.compare(o1,o2);
        }
    });

• Integer의 compare의 값이 default로 들어가게 되는데 이 값을 -로 바꾸어 주면 Max Heap이 된다.

최대 힙의 삽입 과정

• 트리의 가장 끝 위치에 데이터를 삽입하고, 부모 노드와 Key 값을 비교하여 클 경우 부모 노드와 자리를 교체하는 것을 반복한다.

최대 힙의 삭제 과정

• 힙은 삭제할 때 최상위 노드를 반환하며 삭제한다. 마치 Queue의 poll()과 같다.
• 최상위 노드를 삭제한 후 최상위 노드에 가장 마지막 위치의 노드를 위치시킨다.
• 그 후, 삽입과 반대의 과정으로 자식 노드와 비교하며 자리를 교체한다.

(좌, 우 노드와 비교하여 더 큰 값과 자리를 교체한다.)

우선순위 큐**(Priority Queue)**

• 자바에서는 우선순위 큐**(Priority Queue)라는 자료구조 라이브러리로 힙을 지원한다.**
• 힙을 지원한다기 보다는, 우선순위 큐가 우선순위를 선정할 때 힙 방식으로 정렬한다.
• 우선순위 큐는 큐와 비슷하지만, 선입선출 구조인 큐와 달리 큐에 들어있는 자료 중 우선순위를 설정하여 우선순위가 좋은 순서대로 poll()하는 구조이다.

 

회고

발생한 문제

- 자료구조에 대한 공부가 필요하다는 생각이 들었다.

 

해결 방법

- 자료구조 힙에 대해 공부했다. 

 

알게된 내용

- 자바에서는 힙을 우선순위 큐라는 자료구조로 사용한다는 사실을 알게 되었다. 

 

 

참고 자료

- https://velog.io/@suk13574/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0Java-%ED%9E%99heap

- https://velog.io/@dawonseo/Java-%ED%9E%99-%EC%B5%9C%EB%8C%80-%EC%B5%9C%EC%86%8C-%ED%9E%99-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0