목록힙 (1)

말랑말랑한 개발자 이야기

[코테를 위한 압축 개념] C++ STL 힙(Heap), 우선순위 큐(Priority queue)

[코테를 위한 압축 개념] C++ STL 힙(Heap), 우선순위 큐(Priority queue) Heap Heap(힙)은 이진 트리 자료구조이다. 사진으로 보면 이해가 빠르다. - index 0은 최상단 노드임을 의미한다. - i 번째 노드의 자식 노드는 i * 2 + 1 번째 노드와 i * 2 + 2 번째 노드가 된다. - i 번째 노드의 부모 노드는 (i - 1) / 2 번째 노드가 된다. - 부모노드는 항상 자식 노드보다 작거나 같다. / 크거나 같다. 위 사진에서 트리 구조를 살펴보면 부모노드는 자식노드 보다 작은 규칙이 있다. 이러한 구조를 Min Heap이라고 한다. Heap은 두가지의 경우로 나뉘는데 위 사진과 반대로 부모가 자식보다 항상 큰 규칙을 가지면 Max Heap이 된다. 이러한 ..
알고리즘/개념 2021. 1. 6. 17:50
이전 Prev 1 Next 다음