추상적인 데이터 타입(Abstract Data Type)과 자료 구조(Data Structure)의 차이

자료구조를 배우다 보면 우선순위 큐(Priority Queue)와 힙(Heap)을 접하게 된다.

그리고, 힙(Heap)에 대해 공부하다보면 다음과 같은 문장을 무조건 보게 된다

 

 힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다

우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수 있다

분명, 하나의 자료구조를 통해 다른 자료구조를 구현할 수 있다? 문듯 감이 오면서도 정확히 이해가 가지 않는 말이다. 

따라서, 우선순위 큐와 힙 간의 정확히 어떤 차이가 있기 때문에 저런 문장들이 나올 수 있는지 알아보자

 

 

우선순위 큐(Priority Queue)와 힙(Heap)

큐(Queue)

○ 우선순위 큐(Priority Queue)

  - 데이터의 우선순위에 따라 요소들을 저장하고, 가장 높은 우선순위를 가진 요소를 효율적으로 추출하는 추상 자료형(Abstract Data Type)

 

○ 힙(Heap)

  - 일반적으로 완전 이진 트리(Complete Binary Tree)를 기반으로 구현된 자료 구조(Data Structure)

  - 힙은 다음과 같은 특징을 가진다

    1. 최대 힙(Max Heap): 부모 노드는 항상 자식 노드보다 크거나 같은 값을 갖는다

    2. 최소 힙(Min Heap): 부모 노드는 항상 자식 노드보다 작거나 같은 값을 갖는다

  - 또한, 힙은 주로 다음과 같은 연산을 효율적으로 수행할 수 있다

    1. 요소 삽입

      - 트리의 마지막 노드에 새로운 요소를 삽입하고, 필요한 경우 이진 트리의 구조를 유지하기 위해 힙 구조를 재정렬

    2. 최대/최소 값 추출(삭제)

      - 힙의 루트 노드에는 최대값 또는 최소값이 위치하므로, 추출 시에는 해당 값을 반환하고 힙 구조를 재조정

 

 

그렇다면, 추상적인 데이터 타입(Abstract Data Type)과 자료 구조(Data Structure)는 무엇일까?

 

 

추상 자료형(Abstract Data Type)과 자료 구조(Data Structure)

○ 추상 자료형

  - 데이터와 연산들의 집합을 정의한 것

  - 어떤 데이터와 어떤 연산들을 지원하는지에 대한 개념적인 틀

  - 구체적인 내부 구현에 대해서는 명시하지 않으며, 오로지 데이터와 연산들의 관점에서 정의

  - 예: 스택(Stack), 큐(Queue), 우선순위 큐(Priority Queue) 

 

○ 자료구조

  - 실제로 데이터를 저장하고 조작하기 위한 방법이나 형태

  - 데이터의 표현 방식과 데이터 간의 관계, 연산을 수행하는 알고리즘 등을 포함

  - 데이터를 효율적으로 조작하고 저장하기 위한 목적으로 설계

 

요약하자면. 추상자료형은 개념적인 특(모델)이라면 자료구조는 추상 자료형을 '구현'하는 방법이다

 

 

결론

힙은 우선순위 큐(추상 자료형)의 구현 하는 대표적인  방법(자료구조) 중 하나이다