자료구조 Heap에 대해서 알려주세요

[Seobway23]

Heap

힙은 트리 기반 자료구조입니다. 완전 이진 트리 형태로, 모든 노드는 자신의 자식 노드보다 크거나 같은 (최대힙), 또는 작거나 같은(최소힙)의 값을 가집니다. 삽입과 삭제 연산이 빈번히 일어나며, 동시에 최댓값, 최솟값에 빠르게 접근해야 할 때 효율적인 자료구조입니다.

삽입

• 새로운 요소가 힙에 추가될 때, 가장 마지막 위치에 삽입되어, 부모 노드와 비교하면서 위치교환(up-heap, heapify-up) 과정을 거칩니다.
• O(logN)의 시간복잡도 : 최악의 경우 힙의 높이만큼 반복됩니다. ( 완전 이진트리이기 때문에 1/2 )

삭제

• 힙에서 요소를 삭제하는 경우, 보통 루트 노드가 삭제됩니다. 삭제 후, 마지막 요소를 루트로 이동시킨 후, 힙 속성 만족을 위해 자식노드의 위치 교환(down-heap, heapify-down) 과정이 이루어집니다.
• O(logN)의 시간 복잡도: 최악의 경우 힙의 높이만큼 반복됩니다.

접근

• 최대, 최솟값의 경우, 루트 노드에 접근하기 때문에 O(1)의 시간복잡도를 가집니다.
• 임의 값은 전체 요소를 확인하기 때문에 O(N)의 시간복잡도를 가집니다.

[kimmainsain]

답변

• 완전 이진 트리 기반의 자료구조이며, 우선순위 큐(Priority Queue)를 구현하는 데에 자주 사용됩니다.
• 힙정렬 알고리즘은, 힙 구성 O(logN)과 삽입과 삭제 O(logN)으로 O(nlogN)의 시간복잡도를 가지기 떄문에 최악의 경우에도 O(nlogN)을 보장하는 특징이 있습니다.

[freakFlow]

답변

힙 자료구조는 최댓값 및 최솟값을 빠르게 찾아내기 위해 고안된 완전이진트리 기반의 자료구조입니다. 우선순위 큐를 구현하는데 자주 사용합니다.