자료구조 - 힙(Heap)

- 우선순위 큐(Priority Queue) 우선순위를 가진 원소를 삽입할 수 있고, 우선순위가 가장 큰 원소를 빼내줄 수 있는 것을 말한다. - 힙(Heap) 우선순위 큐의 목적인 우선순위를 가진 원소를 삽입하고 삭제하는 것을 아주 효율적으로 다룰 수 있는 자료구조이다. 힙은 완전 이진 트리(Complete Binary Tree) 구조를 사용한다. 힙의 조건은 아래와 같다. 완전 이진 트리 모든 노드는 값을 갖고, 자식 노드 값보다 크거나 같다. - 힙의 특성 완전 이진 트리를 배열로 표현할 수 있다. 배열 A[] 로 표현하면 아래 그림과 같이 A[k]의 부모 노드는 A[(k-1)/2]이고 자식노드는 A[2k+1]과 A[2k+2]이다. - PriorityQueueInterface public inter..

원문링크 : 자료구조 - 힙(Heap)