[자료구조] 힙 (Heap)

개념

힙은 우선순위 큐를 효율적으로 구현하기 위한 자료구조로 이진 트리의 일종이다.

성질

• 힙-순서 특성(Heap-Order Property): 힙 T에서 루트를 제외한 모든 노드 v에 대하여, v에 저장된 키는 v의 부모에 저장된 키보다 크거나 같다.(단, 힙의 정의에 따라 부모 노드에 최대값이 저장될 수도 있다.)
• 완전(complete) 이진 트리 특성: 만약 레벨 0, 1, 2, ..., h-1들이 가질 수 있는 최대 수의 노드를 포함하고 (즉, 레벨 i는 2ⁱ 노드를 포함, 이때 0≤i≤h-1) 레벨 h-1에서 모든 내부 노드는 외부 노드들의 왼쪽에 위치한다면, 높이 h인 이진 트리 T는 완전하다.
• 힙의 높이(height): T의 높이를 h라 할 때 T의 마지막 노드는 레벨 h에 있으며 같은 레벨의 다른 노드들이 모드 그것의 왼쪽에 있다. 이때 h는 log(n)의 정수부이다.
• 원소를 추가, 삭제 하는 과정에서 다운-힙 버블링(down-heap bubbling)이 일어난다.

추상 데이터 타입(ADT)

• insert(val): 힙에 원소 val을 추가한다.
• pop(): 힙의 최상위 원소를 삭제한다.

구현

C++에서 vector, priority_queue 등을 이용해 구현할 수 있다.