개인 공부/Data Structure

Heap

자료구조 ‘힙(heap)’ 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙은 일종의 반정렬 상태를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. Heap은 Full Binary Tree 혹은 Complete Binary Tree에서 작동한다. 비어있는 층의 node들은 주로 NULL Pointer로 생각을 해서 구현을 한다. 이러한 Heap은 다른 자료구조들과 다르게 동적할당이 필요..