[자료구조] 힙 (Heap)

힙(Heap) 구조란?

힙은 우선순위 큐를 구현하는 데 자주 이용된다. 이러한 자료구조에서는 제거되는 원소가 모든 원소들 중에서 가장 높은(또는 낮은) 우선도를 갖는다. 힙에 대한 정의는 다음과 같다. 본 게시물은 최대 힙을 기준으로 작성했다.

정의

최대 트리(Max Tree)는 각 노드의 Key 값이 그 노드의 자식 노드보다 항상 큰 노드이다. 최대 힙(Max Heap)은 최대 트리이면서 동시에 완전 이진 트리인 자료구조를 의미한다. 

최대 힙의 예시

 

삽입 (Insertion)

힙 구조에서 삽입은 다음과 같이 이루어진다.

삭제 (Deletion)

힙에서의 삭제는 다음과 같이 이루어진다.

 

 

※ 본 게시글은 『Fundamentals of Data Structures in C』 를 참고하여 작성되었습니다.