힙

Heap(힙)

Heap(힙) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 💡 완전 이진 트리 : 이진 트리의 일종으로, 자식은 왼쪽부터 연결한다. (왼쪽 자식이 없으면서 오른쪽 자식이 존재할 수 없다) 일종의 반정렬 상태를 유지한다. 부모와 자식간에 정렬된 상태지만, 형제 노드간의 정렬은 이루어지지 않은 상태다. 중복된 값을 허용한다. (이진 탐색트리는 중복허용 X) 힙 종류 최대 힙(Max Heap) 부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리 최소 힙(Min Heap) 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리 힙 구현 일반적으로 배열을 사용한다.(연결 리스트로 구현할 수도 있긴 하다.) 구현의 편의성을 위해 0번 인덱스는 사용하지 않는다. 일정한 규칙을 유지한다...