우선순위 큐와 힙

1. 우선순위 큐와 힙

큐와 우선순위 큐는 다르다. 큐는 선형 자료구조에 속한다.

우선순위 큐는 비선형 자료구조에 속한다

큐의 연장선이 아닌 트리의 연장선이라고 봐야한다

우선순위큐는 들어가는 순서와 나가는 순서가 아무런 관계가 없다

단지 입구와 출구가있어서 큐라하는것이다.

우선순위를 근거로 데이터 뽑아낸다.

우선순위는 프로그래머가 결정함.

2. 우선순위 큐의 구현

1)   배열과 연결리스트로 구현 

데이터의 수가 많아지면

 배열이나 연결리스트는 성능이 떨어진다

 그래서 힙을 이용해 구현하는게 좋다

2)   힙이라는 자료구조를 통한 우선순위 큐 구현

힙이 우선순위큐라고 말할수는 없다. 우선순위 큐를 만들기 위해 힙(이진트리)을 사용한것이다.

힙의 특성 2가지

- 이진트리의 일종이다 그런데 그냥이 아닌 완전 이진트리이다

 위에서 아래로 왼쪽에서 오른쪽으로 데이터를 꽉채워서 차곡차곡 쌓아가는걸 완전이진트리라함

-그리고 힙은 루트 노드에 저장된 값이 우선순위가 가장높음

 최대힙일때 모든 노드는 자식노드에 저장된 값보다 크거나 같아야 한다

 최소힙일때 모든 노드는 자식노드에 저장된 값보다 작거나 같아야 한다.