1회차(12.28) - 결과

 

결과 : 

 

힙(Heap)은 최댓값과 최솟값을 쉽게 찾아내기 위해 사용한다.

 

최소힙과 최대힙이 있는데,

부모노드가 자식노드보다 작으면 최소 힙(MinHeap)이고, 

부모노드가 자식노드보다 크면  최대 힙(MaxHeap)이다.

 

 

*삽입:

 

힙은 완전 이진 트리의 구조를 유지해야한다.

따라서 삽입 할 때 트리의 가장 마지막에 원소를 추가한다.

그 후 힙의 조건이 맞는 지 확인한다. !

예를 들어, maxheap의 경우,

마지막에 원소 추가 한 후에 부모노드와 검사를 해서

조건이 맞지 않으면(부모노드가 더 작은경우) 자리를 바꾼다.  

그리고 조건이 맞을 때 까지 반복하여 검사한다.

루트 노드에 위치하게 되는 경우에는 더 이상 검사를 하지않고 끝난다.

 

 

*삭제:

 

삭제연산은 루트에서 이루어진다.

루트에서 노드가 삭제된 후, 가장 마지막 노드를 루트로 옮긴다. 이는 완전 이진 트리를 유지하기 위함이다.

루트로 옮겨지면 자식노드와 비교하여 힙 조건을 검사한다.

조건이 맞지않으면 루트노드와 자식노드를 바꿔준다.

힙 조건을 만족할 때 까지 조건검사를 반복하여 진행한다.

 

 

+ 

 

대표적으로 힙을 활용하는 것이 우선순위 큐가 있다.

 

* 우선순위 큐가 사용되어야 하는 경우 ?

  -> 원소를 삽입, 삭제 후 매번 정렬을 해야하는 문제 !

  -> Collections.sort와 같은 퀵 정렬을 사용하면 시간복잡도가 nlogn으로 커지게 된다.

  -> 우선순위 큐를 사용하면 원소 삽입 또는 삭제 시 logn의 시간복잡도로 정렬할 수 있음 !

 

*PriorityQueue 사용법

 

  일단 PriorityQueue를 import 해준다.

 

  그 후 타입에 따라 선언을 해준다.

  ex ) int형의경우

  PriortyQueue<Integer> pq = new PriorityQueue<>();

  와 같이 선언한다.

 

  - 삽입 : add()

    ex) pq.add(1) 을 해주면 1이 삽입된다.

 

  - 삭제 :  poll(), remove() - 우선순위 가장 높은 값 제거(루트)

    poll() : 값을 반환하고 제거, 비어있다면 null

    remove() : 제거 (반환 x )

 

 

 

삽입, 삭제 과정을 그림도 그려보고, 구현 된 코드를 살펴보며 알고리즘 및 자료구조 시간에 다루었던 heap에 대해 복습할 수 있었다.

 

다음 시간에는 이를 바탕으로 알고리즘 문제를 풀어 심화시켜보고자 한다. !