우선순위 큐 정리

우선순위 큐 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

구현 방법 

1. 배열 기반 

2. 힙 기반 

3. 링크드 리스트 기반

하지만 1번과 3번 같은경우 두가지 큰단점이 있다 

1.데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야한다 

2. 삽입의 위치를 찾기 위해서 배열에 저장된 모든데이터와 우선순위의 비교를 진행해야 할 수도 있다,

힙 의 종류 - 최대힙(루트값이 가장 크다) , 최소힙(루트가 가장 작다) 

이러한 단점을 극복하기위해 우선순위 큐는 주로 힙으로 구현된다 

주의 해야할 점은 힙과 우선순위 큐를 동일하게 인식 하면 안된다 .

즉 우선순위 큐와 힙을 어느정도 구분 할 줄 알아야한다 . 

힙은 우선순위 큐의 구현에 딱 어울리는 완전 이진트리의 일종이라는 사실을 기억해야 한다.

우선순위큐를 구현하기위해서 

1. 힙을 구현 

2. 힙 구현 기반으로 우선순위 큐 구현

1.힙 구현 삽입시

힙을 구현 하기위해서는  마지막 위치(마지막 레벨 노드에 오른쪽 위치)에 노드 추가 한후  그리고 마지막위치에 추가한 노드와 그의 부모노드를 계속해서 비교해서 제대로된 위치에 위치 시킵니다.

2. 힙 구현 삭제시 

-1 루트 삭제 

-2 맨 아래 레벨의 오른쪽 노드를  비어져 있는 루트에 옮겨 놓고 옮겨진 루트의 자식노드 두개중에 우선순위가 높은것과 비교해서 올바른 자리를 자리를 찾아간다 .

힙을 구현을 할려면 링크드리스트 ? 배열 ? 어느것이 원칙일까?

답은 배열이다 

왜냐하면  연결리스트를 기반으로 힙을 구현 하면 새로운 노드를  힙의 마지막의 위치에 추가 하는것이 쉽지 않다 .

이어서 http://lemeraldl.tistory.com/admin/entry/post/?id=171