Heap<힙>

자료구조 중 힙(Heap)은 특정한 순서에 따라 정렬된 요소들을 저장하는 트리 기반의 자료구조.

Heap 은 일반적으로 이진 힙(binary heap)으로 구현되며, 우선순위 큐(priority queue)와 같은 다른 추상 자료형의 구현에 주로 사용된다.

 

Heap은 다음과 같은 특징을 가지고 있다.

• 완전 이진 트리(Complete Binary Tree) : Heap 은 완전 이진 트리의 형태를 가진다. 이는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워져 있는 형태를 말한다.
• 부모-자식 노드 관계 : Heap의 부모 노드는 항상 자식 노드보다 우선순위가 높거나 같은 값을 가진다. 이러한 특성은 최대 힙(max Heap)에서는 부모 노드가 항상 자식 노드보다 큰 값을 가지며, 최소 힙(min heap)에서는 부모 노드가 항상 자식 노드보다 작은 값을 가지는 것을 의미한다.
• 힙 속성: Heap의 모든 부모-자식 쌍에 대해 특정한 조건을 만족해야한다. 최대 힙에서는 모든 부모 노드가 자식 노드보다 크거나 같은 값을 가져야 하며, 최소 힙에서는 부모 노드가 자식 노드 보다 작거나 같은 값을 가져야 한다.

Heap은 주로 다음과 같은 연산을 지원한다.

• 삽입 : Heap에 새로운 요소를 추가한다. 일반적으로 우선순위 큐에서는 우선순위에 따라 요소가 삽입된다. 
• 삭제 : Heap에서 가장 우선순위가 높은 요소를 삭제한다. 최대 힙에서는 가장 큰 요소가 삭제되고, 최소 힙에서는 가장 작은 요소가 삭제된다.

장점과 단점을 알아보자.

장점

• 빠른 삽입 및 삭제 : Heap은 특정한 순서에 따라 정렬된 상태를 유지하므로 삽입과 삭제 연산이 상수시간에 이루어진다. 이는 요소들의 우선순위에 따라 빠르게 작업을 처리 할 수 있다는 것을 의미한다.
• 우선순위 기반 작업 처리: Heap은 우선순위 큐와 같은 다른 추상 자료형을 구현하는데 사용된다. 최대 힙인 경우에는 가장 큰 우선순위를 가진 요소에 빠르게 접근 할 수 있고, 최소 힙인 경우에는 가장 작은 우선순위를 가진 요소에 빠르게 접근할 수있다. 이를 통해 우선순위에 따라 작업을 관리하고 처리할 수 있다.

단점

• 임의 접근 어려움 :Heap은 일반적으로 완전 이진 트리의 형태를 가지며, 배열 또는 연결 리스트를 사용하여 구현된다. 이러한 구조는 임의 접근을 지원하지 않고, 요소에 접근하기 위해 순차적인 탐색을 수행해야 한다. 따라서 특정한 요소를 찾는데에는 O의 시간이 걸린다.
• 정렬 유지의 오버헤드 : Heap은 정렬된 상태를 유지하기 위해 삽입과 삭제 연산 시에 정렬을 조정 해야한다. 이는 일정한 오버헤드를 발생 시킬 수 있다. 따라서 요소들의 정렬 상태가 항상 필요하지 않은 경우에는 다른 자료구조를 고려하는 것이 좋다.
• 배열로 구현시 추가적인 공간 요구 : Heap은 일반적으로 배열 또는 연결 리스트를 사용해 구현된다. 배열 기반 Heap에서는 공간을 미리 할당해야 하므로 요소의 개수에 따라 적절한 크기를 선택해야 하며, 요소의 개수에 따라 추가적인 공간을 필요로 한다.

위의 내용은 블로그 https://hoehen-flug.tistory.com/32

[자료구조] 힙(Heap) 자료구조 알아보기 & Java 예제 코드

를 참조하여 공부한 내용입니다. 

결과적으로 데이터의 최댓값과 최솟값을 찾기 쉬운 PriorityQueue 는 완전 이진 탐색 구조로 Heap이다.