[C++] 힙 (Heap)

힙 (Heap)

완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드(최대 힙 / max heap)나

키값이 가장 작은 노드(최소 힙 / min heap)를 찾기 위한 자료구조

힙은 우선순위 큐(priority Queue)라고도 한다

 

STL에서는 std::priority_queue로 구현

 

 

힙의 불변성

힙은 특정 조건을 만족해야 한다.

 

1) 최대 / 최소 원소에 즉각적으로 접근이 가능해야 한다.

( 최대 / 최소 원소가 항상 루트 노드에 존재하고 있다.)

 

2) 부모 노드가 두 자식 노드보다 항상 크거나 작아야 한다.

( 힙은 부모 기준으로 크거나 작으면 된다. 이진 검색 트리의 조건을 충족하지 않아도 된다.)

 

연산

 

검색 및 읽기

최대 / 최소 원소에 대해서만 가능하며 루트노드에 존재하여 O(1)이다.

 

삽입

완전 이진 트리이기 때문에 O(log n)이다.

 

삭제

최대 / 최소 원소에 대해서만 가능하며 O(log n)이다.

 

 

 

트리는 순차/연결로 구현할 수 있는데,

메모리를 효과적으로 사용하기 위해 연결 자료구조를 사용한다.

순차 자료구조로 구현되면 메모리에 낭비가 발생한다.

 

힙은 배열로 구현한다.

꽉꽉 들어가 있어서??