배열을 이용한 힙(Heap) 구현

배열을 이용한 힙(Heap) 구현

 

배열을 이용했을때의 특징

• 힙의 삽입 과 삭제 연산이 더 빠르다.
  • 노드의 주솟값을 계산할 수 있어 원하는 노드에 빨리 접근할 수 있다.
• 힙은 완전 이진 트리(Complete binary tree)이기 때문에 낭비되는 빈 노드가 적어 공간의 낭비가 적다.

 

배열의 위치 인덱스와 히프

 

• 루트 노드의 위치 인덱스의 값은 1
• 노드 i 의 부모 노드 인덱스 = [i / 2] , i>1 일때
  • ex) [5 / 2] = [2.5] = 2
• 노드 i 의 왼쪽 자식 노드 인덱스 = 2 * i
• 노드 i의 오른쪽 자식 노드 인덱스 = (2 * i) + 1

각 노드의 위치 인덱스 계산

 

Max Heap 에 데이터 삽입하기

기본 원리

1. 새로운 노드를 마지막 노드 옆에 삽입한다.
2. 새로운 노드의 값을 부모 노드의 값과 비교하여 위치를 이동한다.

 

삽입 연산

1. i 는 히프의 마지막 노드의 위치를 가리키는 인덱스로 설정
   • i = pHeap->currentCount
2. 반복 조건 설정
   1. 현재 노드의 위치가 루트가 아니라면
      • i != 1
   2. 새로 추가된 데이터의 값이 부모 노드이 값보다 크다면
      • value > pHeap->pData[i/2].data
3.  명령 실행

    

   1. 부모 노드의 값을 현재 노드의 위치로 이동한다.
      • pHeap->pData[i] = pHeap->pData[i/2]
   2. 현재 노드를 부모 노드의 위치로 이동한다.
      • i /= 2

새로운 값을 삽입

데이터 삽입 과정

데이터 삽입 완료

Max heap 재구성

 

Max Heap 에서 데이터 제거하기

기본 원리

1. 최댓값을 가진 루트 노드를 제거
2. 마지막 노드를 루트 노드에 삽입
3. Max heap 의 조건을 만족하기 위해 노드를 이동해 재구성한다.

제거 연산

1. 변수를 선언한다
   1. pTemp 로 제일 마지막 노드를 가리키게 한다.
      • pTemp = &(pHeap->pData[pHeap->currentCount])
      • parent = 1 과 child = 2 로 선언해 각각 루트 노드와, 루트 노드의 왼쪽 자식 노드를 가리키도록 한다.
2.  반복 조건 설정
   1. child가 제일 마지막 노드를 만날때 까지 루프를 돈다.
      • child <= pHeap->currentCount
3.  명령 실행
   1. 자식 노드의 키 값을 비교하고 노드를 이동시킨다.
      • child 가 가리키는 왼쪽 자식 노드의 값보다 오른쪽 자식 노드의 값이 더 크면 child의 위치 인덱스를 수정한다.
      • pHeap->pData[child].data < pHeap->pData[child+1].data

루트 노드 제거후 마지막 노드를 이동

더 큰 값을 가진 자식 노드와 교환

Max heap 재구성

 

 

구현 소스

GitHub