파이썬) 힙과 우선순위 큐가 헷갈리는 사람들을 위한 정리!

핵심 내용인 힙과 우선순위 큐를 먼저 작성하고

그 다음 간단한 개념들을 작성 및 나열해두었습니다.

---

우선순위 큐란?

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

 

우선순위 큐 구현방법은?

힙의 값(key)를 우선순위로 사용하게 되면,

힙은 우선순위 큐의 구현체가 된다.

 

그러면 힙(HEAP)은 우선순위 큐 인가요? -> 아니다!!! 

우선순위 큐는 ADT이다.

ADT는 Abstract Data Type(추상 데이터 타입) 의 약자로,

동작의 개념적인 것들만 설명을 해둔것이다.

 

그러나 힙은 Data Structure(자료구조)이다.

즉 구현까지 가능한 것이다.

그래서 정확히 말하자면 힙은 우선순위 큐의 구현체 라고 할 수 있다.

 

 

 

아니 그러면 그냥  대충 우선순위 큐랑 힙이랑 같다고 해도 되지 않나요?

-> 안된다!!

배열과 연결리스트 자료구조로도 우선순위 큐를 구현할 수 있으므로,

힙은 그냥 우선순위 큐를 구현할 수 있는 수단 중 하나라고 생각하여야 한다.

예를들어 피자를 만드는데 도미노피자에서 만든 피자랑 피자헛이 만든 피자랑 

같은 피자라고 할 수는 없는 것이랑 똑같은 이치이다.

 

---

기타 개념 설명

 

힙 (Heap)

완전 이진 트리 자료구조의 일종이다. 

항상 루트 노드를 제거한다.

 

이진트리란? 노드의 자식이 최대 2개인 트리

완전 이진트리란? 마지막 레벨을 제외하고 모든 레벨이 채워진 트리. 이때 좌측노드부터 채워나감.

 

최소 힙 (Min Heap)

부모 노드의 키 값이 자식노드보다 같거나 작은 완전 이진트리

 

최대 힙 (Max Heap)

부모 노드의 키 값이 자식노드보다 같거나 큰 완전 이진트리

 

힙의 삽입

최소 힙이든 최대 힙이든 공통적으로,

1. 힙의 마지막 위치에 삽입.

2. 새로 온 힙을 부모 노드들과 교환하며 힙의 성질을 만족시킨다.

 

힙의 삭제

최소 힙이든 최대 힙이든 공통적으로,

1.루트 노드를 삭제.

2.삭제한 루트노드에 힙의 마지막 위치 노드 가져옴

3.힙의 성질을 만족할때까지 교환

 

힙의 peek

삭제와 동일하게 루트노드를 가져오지만, 삭제는 하지않음.