어딘가 잘못된 힙...(진짜 잘못됨)

우선순위 큐는 일반적인 큐와 달리 철저히 우선순위에 의해 동작한다.

우선순위를 설정하는 방법은 여러가지가 있다.

간단하게 우선순위를 정할 경우, 리스트를 이용해도 된다. 

List<Node> list = new ArrayList<>();
Collections.sort(list);

이런식으로 작성하면 리스트로 우선순위 큐를 만들 수 도 있다. 
하지만 리스트로 이용할시, 많은 시간이 발생한다.

그래서 리스트보다는 힙 자료구조를 이용해서 우선순위 큐를 이용한다.

즉, 이름은 큐이지만 사실은 힙인듯 싶다.

보통 힙 알고리즘은 이런식으로 시작된다. 하지만 이건 아직 힙 정렬을 하지 않는 상태다.

위는 완전 이진 트리라고 하는데 이 부분은 추후에 설명할지도 모르겠다. 아무튼

힙 정렬은 2가지로 구분되는데, 최소 힙정렬과 최대 힙 정렬이 존재한다. 

최소 힙정렬를 해보자.

1이 가장 작기 때문에 1은 삭제한다.

그러면 

이런식으로 노드가 끊긴다. 이럴때는 가장 마지막 값을 추가해주면 된다.

근데... 이건 정렬이 되지 않는 상태다. 두 노드모두 8보다 작다. 그렇기 때문에 이 둘중 더 작은 값으로 교체 해주면 된다.

자 이런식으로 계속 정렬을 해보자.

첫 번째 정렬이 끝났다. 처음 노드의 총 개수 는 6개다.

만약 이걸 버블 정렬로 정렬을 했다면 O(n^2)이 걸리기 때문에 시간은 36정도 걸린다.

아... 한번 정렬하는데는 n번이 걸리기 때문에 6이다.

그렇다면 힙정렬은 몇번만에 완성이 되었을까?

1을 그렇다고 치고,, 총 2번의 연산으로 연산이 종료되었다.
만약, 1도 정렬이 되어있지 않는다면, 2번의 연산이 되지 않을까 추측한다.
가로는 변환 횟수다.

계산 할려구 했는데 생각보다 쉽지 않다. 그래서 다음것도 쭉쭉 해보자. 

3도 최대 2번

1번

1번

 

0번

1부터 3까지 전부 2번 그다음은 4,5는 1번 8은0번의 시간이 걸린다.

이제 이들을 더해보자 최대 8의 시간이 걸린다는것을 알 수 있다.

노드의 갯수가 6이기 때문에 시간은 조금 걸린건 사실이지만...

logN정도가 걸린다고 알고 있는데... 생각보다 크게 걸리는 것 같다. 

이는 2가지로 해석 될수 있다. 이게 맞다면 내가 잘못 본거 일 수 도 있고,

아니라면 계산이 잘못한 것 같다.

나중에 다시 해봐야 겠다.