Heap

소개

 

Heap이란 자료구조는 최대 최솟값을 구하기 위해 고안된 완전 이진 트리(마지막 레벨을 제외한 모든 노드가 꽉차 있는 노드 마지막 노드는 왼쪽부터 차있어야 한다.)

 

입니다.

 

Root 노드를 제외한 모든 노드는 오름차순 혹은 내림차순이고, 마지막 왼쪽 노드를 제외한 모든 레벨은 완전 이진 트리를 형성한다.

 

때문에 Root 노드의 값이 최댓값 혹은 최솟값일 수 밖에 없습니다.

 

Heap은 트리지만 일반적으로 노드로 구현되는 트리들과 달리 배열로 구현합니다. (배열로 구현할 경우 일반적인 트리는 완전 이진트리가 아니므로, 메모리의 낭비를 가져

 

온다. 배열에서 사용하지 않는 공간이 중간에 생기기 때문)

 

이유는 Heap을 노드로 구현하면 트리의 마지막 레벨의 왼쪽부터 노드를 추가하기가 힘듭니다.

 

배열로 구현할 경우 배열에 마지막에 넣어주면 트리의 왼쪽부터 넣어주는 것과 같은 효과를 낼 수 있습니다.

Heap을 이용하여 Heap Sort(Heap을 정렬하는 것)를 구현할 수도 있는데 이는 나중에 자세하게 설명해 드리도록 하겠습니다.

 

우선순위 큐가 Heap로 구현되어있다고 많이들 아시는데, 사실상 우선순위 큐는 map과 같은 레드블랙트리로 이루어져 있습니다.

 

구현

 

Node

 

 

 

Key : 데이터를 찾아오고 정렬할 Key값

 

data : 내가 저장할 데이터

 

Member Variable

 

 

 

m_pArr : 배열의 주소

 

m_iCount : 현재 데이터의 갯수

 

m_iMaxCount : 최종 사이즈

 

 

Member Functions

 

 

Expand : 가변 배열과 같이 m_iMaxCount 보다 m_iCount가 크거나 같을경우 메모리를 확장해준다.

 

UpHeap : 자식이 부모보다 작을 경우 자식과 부모를 바꿔준다.

 

DownHeap : 자식이 부모보다 클 경우 자식과 부모를 바꿔준다.