자료구조 - Heap

 

 

Heap 이란 ?

 

 

Heap은 완전 이진 트리(Complete Binary Tree)*의 형태를 가진 자료구조 이며 여러 데이터들 중 최소값 데이터 혹은 최대값 데이터를 빠르게 찾기 위해 고안한 자료구조다.

 

 

(완전 이진 트리 : 트리의 모든 레벨이 꽉 채워져 있으며 왼쪽부터 오른쪽으로 채우는 트리)

 

 

 

 

Heap의 특징

 

 

 

• 힙은 완전 이진 트리의 형태를 가진다.

 

• 부모노드의 값이 자식노드의 값보다 큰 경우 최대 힙으로 표현한다.

 

• 자식노드의 값이 부모노드의 값보가 큰 경우 최소 힙으로 표현한다.

 

• 힙을 구현할때는 배열을 이용하여 구현한다.

 

• 힙에 데이터를 삽입하거나 삭제한 후에는 꼭 HeapifyUp이나 HeapifyDown을 사용하여 힙의 속성이 깨지지 않도록 한다.

 

• 힙은 모든 언어에서 기본 라이브러리로 지원하지 않는다.
  (C#이나 Javascript에서는 외부 라이브러리를 추가하거나 직접 구현해주어야 함.)

 

 

우선순위 큐 vs Heap

 

 

우선순위 큐 (Priority Queue)

 

 

우선순위 큐는 데이터를 저장하는 방식은 큐(FIFO)와 동일하지만 데이터를 삽입하거나 삭제하는 동작 방식과 우선순위에서 차이가 있다.

 

 

Queue는 Enqueue시 무조건 맨 뒤에 데이터를 추가하고 Dequeue시에는 맨 앞에서 데이터를 추출하지만

우선순위 큐는 최댓값 혹은 최솟값 같은 우선순위를 먼저 부여하고 해당 우선순위에 따라 데이터를 추출한다.

 

 

큐는 데이터 삽입, 삭제시 항상 O(1) 의 시간복잡도를 가지지만
우선순위 큐의 경우 O(logN)을 가진다. (힙을 이용하는 경우)

 

 

또한 우선순위 큐는 추상 데이터 타입(ADT)으로 우선순위 큐를 구현하는 방식이 특정 자료구조나 데이터 타입에 의존하지 않고 다양한 방식으로 개념이나 인터페이스를 정의할 수 있는 개념이다.

 

 

 

대부분의 우선순위 큐는 힙을 이용하여 구현한다.

 

 

우선순위 큐와 힙의 차이점

 

 

우선순위 큐를 구현하는데에 있어서 추상 데이터 타입이라는 점에서 차이점이 발생한다.

 

우선순위 큐를 구현 하는 방식 중 힙을 이용하는것은 시간 복잡도 적인 측면에서 다른 자료구조를 사용하는 것 보다 경제적인 경우가 많아서 힙을 사용하지만 꼭 힙을 사용해서 우선순위 큐를 구현해야 하는것은 아니다.

 

 

정리하자면

 

 

• 우선순위 큐는 요소의 우선순위에 따라 처리 순서가 결정되는 추상 데이터 타입이다.
• 힙은 우선순위 큐를 효율적으로 구현할 수 있는 자료구조다.
• 우선순위 큐는 힙 외에도 여러 가지 방법으로 구현될 수 있다.

 

 

 

 

 

사진 출처 : https://www.geeksforgeeks.org/

GeeksforGeeks | A computer science portal for geeks