목록Data Structure (1)

미운 오리 새끼의 우아한 개발자되기

[자료구조] 힙 (Heap)

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. 힙에는 두가지 종류가 있다. 최대 힙(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 같거나 큼 최소 힙(min heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 같거나 작음 키 값의 대소관계는 오로지 부모 노드와 자식 노드 간에만 성립하며 형제 사이에서는 대소관계가 정해지지 않는다. 힙 리스트로 표현할 때 i 번째 노드의 왼쪽 자식 노드의 위치는 2i가 되며, 오른쪽 자식 노드의 위치는 2i+1이고 또한 i 번째 노드의 부모노..
Data Structure 2022. 2. 11. 12:49
이전 Prev 1 Next 다음