[알고리즘] 힙-HEAP

힙에 대해 알아보고, 연습문제를 통해 java로 힙을 이용하여 문제를 해결해 보는 시간을 가져보았다.

먼저, 힙이란?

힙은 이진트리의 일종이다.

근데, 우선순위 큐를 위.하.여 만들어진 구조이다.
우선순위큐란? 자료가 들어간 순서와 상관없이 우선순위 데이터가 높은 데이터부터 나오는것을 말한다.
(First In Last/First Out 같은게 아니라, 들어간 순서 자체가 상관없는 Queue.)

시간복잡도

시간복잡도가 우수하기 때문에 Heap을 이용하여 우선순위큐를 만드는 것이 가장 효율적이다.

힙(Heap)의 삽입/삭제

삽입

힙 이진트리에서의 삽입은 맨 마지막 인덱스 위치에 삽입되어, 부모노드와 비교하여 max/min에 따라 크기 비교 후, 위치를 바꾼다.

삭제

코드를 작성하다 보면 알겠지만, 큐에서 삭제란 최상단(Root)에 있는 값을 빼내는 것을 말한다.

그 이후, 힙의 마지막 노드를 Root노드로 가져온다.
자식노드와 비교하며 Switching을 하고, 제 위치를 찾아간다.