우선순위 큐(Priority Queue)와 힙 정렬(Heap Sort)의 차이

우선순위 큐와 힙은 정말 많이 닮았다. 오죽하면 우선순위 큐 = 힙이라고 아는 분들도 적지 않을 것이다.

 

결론만 말하자면 둘의 차이는

우선순위 큐는 ADT(Abstract Data Type)이고
힙은 Data Structure이다.

※큐(Queue) = 먼저 들어오는 데이터가 먼저 나가는 구조(FIFO - First In First Out)

ADT(Abstract Data Type) 

"추상적 자료형"이라는 뜻이다. 있는 그대로를 해석해 보자면 

핵심 개념이나 기능을 간추려 내어 데이터를 식별하는 구분, 연산, 저장 방법 등을 모두 포함한 것
추상화를 통해 얻어낸 자료형

이게 무슨 말이냐면 자료 구조와는 달리 구현내용은 명시하지 않는다. 오로지 인터페이스만 제공할 뿐

특징이 있다.

● 추상화를 통해 정의된다

● 무엇인지는 말해준다 하지만 어떻게 구현하는지는 말해주지 않는 것이다.

● 구현으로부터 분리하고 간단한 인터페이스만 정의하고 세부 내용을 숨긴다는 것이다.

   -- 추상화를 통한 캡슐화가 가능하다는 것(캡슐화가 된다면 정보 은닉이 가능하다)

● 우리가 프로그래밍을 할 때 말하는 inteface 또한 추상 자료형의 한 종류인 것이다.

 

우리가 아는 스택, 큐, 덱, 리스트, 이진트리 같은 자료구조도 추상 자료형이다.

자동 변속기에 대해 설명을 해보자면 

● Data = 변속 모드들 

● Parking(), Reverse(), Neutral(), Drive()

이것들이 모두 추상적 자료형들이 되는 것이다.

 

똑같은 추상적 자료형이랑 비교하여 예를 들어보겠다. 

스택(Stack)의 형태는 LIFO 값들의 모임이다. push, pop, size 등으로 연산을 정의한다. 하지만 스택이 어떤 배열을 사용하는지 연결 리스트로 구현하는지 size연산을 할 때 원소의 개수를 일일이 세는지 개수를 따로 저장해 두는지 알 수 없다.

그것을 우리가 직접 다루기 시작하면 자료구조의 영역으로 넘어가는 것이다.

 

장점 

1. 세부사항은 감추고 인터페이스만 제공함으로 캡슐화가 가능하다  = 정보 은닉이 가능하다
2. 핵심기능은 미리 선언하고 제공하면서 코드가 굉장히 짧아진다. 그래서 코드의 재사용성 및 가독성을 증가시킨다
3. 내부 구현을 사용자에게 맡김으로써 사용의 유연함을 제공할 수 있다. = 다형성

Data Structure

"자료 구조" 우리가 흔히 아는 그 자료 구조이다.

자료구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.

추상 자료형이 정의한 연산들을 구현한 구현체이다.

 

비교점

스택이나 큐는 구현 방법이 전혀 정의되어 있지 않다 == 추상 자료형

배열은 우리가 연속적으로 저장되어 있도록 구현이 되어있어야 한다. == 자료 구조

연결 리스트 또한 다음 데이터의 위치를 저장하는 방식으로 정해져 있다 == 자료 구조

---

꽤 먼 길을 돌아왔지만 아주 중요한 점이니 꼭 짚고 넘어가도록 하자

그럼 위에 이야기를 우선순위 큐와 힙에 적용해 보자

우리는 힙을 적용할 때 상세한 구현을 해야 한다. 즉 힙은 자료구조인 것이다.

하지만 우선순위 큐는 인터페이스를 정의하는 것만으로 사용할 수 있다. 즉 추상적 자료형이다.

 

그도 그럴 것이 우선순위 큐를 구현하는 방식은 힙만 있는 것이 아니다.

 enqueue - 큐에 새 요소를 집어넣는 행위

 dequeue - 큐에서 우선순위 요소를 삭제하고 값을 반환

 peek() - 큐에서 최대 우선순위를 반환한다.

구현 방법	enqueue	dequeue	peek
배열	O(1)	O(n)	O(1)
연결 리스트	O(1)	O(n)	O(1)
힙	O(logn)	O(logn)	O(1)

이런 식으로 우선순위 큐는 구현 방식만 해도 3가지가 있다. 근데 왜 큐는 힙이라고 하는 걸까

바로 시간 복잡도에서 나타난다. 다른 구현 방식과 다르게 힙구조는 어떠한 상황에서도 O(logn)을 유지한다.

※ peek()은 가장 위에 있는 노드이기 때문에 O(1)로 통일이다.

그래서 우리는 우선순위 큐를 생각하면 힙을 생각하게 되는 것이다. 

 

어쨌든 이글의 중점은

추상적 자료형(ADT)인 "우선순위 큐(pq)"의 구현 방법이 힙이 되는 것이지 자료구조(Data Structure)인 "힙(Heap)"이랑 같다고 할 수 없는 것이다.