힙은 추상 데이터 유형으로 간주됩니까?

Question

데이터 구조 코스를 수강하고 있는데 ADT (추상적 데이터 유형)로 간주되는 것과 그렇지 않은 것에 대해 다소 혼란스러워합니다. ADT가 아닌 경우 구현해야합니다. .

특히 저는 힙에 대해 이야기하고 있습니다.

"힙은 특수 트리 기반 데이터 구조입니다"라는 위키 백과에서 읽은 것은 그것이 ADT라는 의미입니까? 그렇다면 Wikipedia에서 다음 줄을 이해할 수 없습니다. "힙은 우선 순위 큐라는 추상 데이터 형식을 최대한 효율적으로 구현합니다."

내 말은, 힙을 ADT로 만들 수 있고 다른 ADT (이 경우 우선 순위 큐 구현)를 구현할 수 있습니까? ADT의 개념을 이해하고 이진 힙의 컨텍스트에서 이것이 가능하다는 것을 이해합니다. arr[i]는 I 힙 다른 ADT 구현 배열 반면에 데이터 구조를 사용하여 구현 한 손 ADT 될 수 있는지 여부에 대해 단지 혼란있어 arr[2i] 및 arr[2i + 1] 의 부모 인 배열을 사용하여 구현.

이것에 대한 설명이 필요하십니까

Answer 1

힙은 추상으로 간주되지 않습니다. 데이터 형식.

힙은 우선 순위 큐라는 추상 데이터 형식의 구현 인 특수 트리 기반 데이터 구조입니다.

는 https://en.wikipedia.org/wiki/Heap_(data_structure)

Answer 2

힙은 ADT하지 않습니다를 참조하십시오. 이것은 데이터 구조입니다.

---

의무적 위키 백과 인용 :

컴퓨터 과학에서

, 추상 데이터 타입 (ADT)는 데이터 유형이 그 동작 (에 의해 정의 된 데이터 유형에 대한 수학적 모델입니다 의미), 특히 (가능한 값),이 유형의 데이터에 가능한 작업, 및 이러한 작업의 동작에 대해 설명합니다. 이는 데이터의 구체적인 표현 인 데이터 구조와 대조되며 사용자가 아닌 구현 자의 관점 인 입니다. 스티브 맥코넬에 의해 -2 전체 코드에서 영감을

---

보너스 콘텐츠입니다.

데이터 구조는 문제 도메인에서 작동하는 ADT와 달리 낮은 수준의 구현 도메인 항목입니다. ADT를 사용하면 하위 수준의 구현 엔터티가 아닌 실제 엔터티를 조작 할 수 있습니다. 노드를 링크 된 목록에 삽입하거나 힙에 항목을 추가하는 대신 스프레드 시트에 셀을 추가하거나 창 유형에 새로운 유형의 창을 추가하거나 열차 시뮬레이션에 다른 승객을 추가 할 수 있습니다.

• 당신은 분명히 등) (getTop) (,),) 그 힙 삽입과 같은 의미를 (정의했다 들여다 heapify를 (볼 수 있습니다- here가 자세하게 나와 있습니다. 따라서 그것은 데이터 구조입니다. 당신은 단순히 가서 폭포 곳의 꼭대기에 앉아하는 새로운 블록을 추가 테트리스의 게임을 시뮬레이션 할 경우

• 그러나,이 테트리스 게임의 UI는 실제로 ADT 될 것입니다.

Answer 3

나는이 혼란에 대해 다른 방법으로 분명히하려고 노력할 것입니다. here에서 위키 피 디아를 인용 :

우선 순위 큐는 종종 힙으로 구현하는 동안, 그들은 힙에서 개념적으로 구별 이다. 우선 순위 큐는 "목록"또는 "맵"과 같은 추상 개념입니다. 리스트가 링크 된리스트 또는 배열을 가지고 으로 구현 될 수있는 것처럼 우선 순위 큐는 힙 또는 정렬되지 않은 배열과 같은 다양한 다른 방법으로 으로 구현 될 수 있습니다.

• 정렬되지 않은 배열
• 정렬되지 않은 목록 :

그래서 힙 아래에 나열된 다른 많은 구현되지 않을 수 있지만 제한 될 수있는 우선 순위 큐 추상 데이터 타입 (ADT)의 단지 구현

는 배열

순서가있는 목록

이진 검색 트리 (BST)

에게 발주

균형 이진 검색 트리 (OP에 의해 요청) (AVL 트리)

진 힙

다른 가능한 구현과 우선 순위 큐 ADT 주요 작업에 대한 힙 구현의 시간 효율성 비교 :

---------------------------------------------------------------------------- 
| Implementation | Insertion | Deletion(DeleteMax/DeleteMin)|Find Max/Min 
---------------------------------------------------------------------------- 
| Unordered Array| 1   | n       | n 
---------------------------------------------------------------------------- 
| Unordered List | 1   | n       | n 
---------------------------------------------------------------------------- 
| Ordered Array | n   | 1       | 1 
---------------------------------------------------------------------------- 
| Ordered List | n   | 1       | 1 
---------------------------------------------------------------------------- 
| BST   | logn (avg.) | logn (avg.)     | logn (avg.) 
---------------------------------------------------------------------------- 
| Balanced BST | log n  | log n      | log n 
---------------------------------------------------------------------------- 
| Binary Heaps | log n  | log n      | 1 

을