비선형 자료구조 - 4. 힙

힙 (Heap)

Heap 예시

 

힙(Heap)이란 여러 개의 값 중에서 가장 크거나 가장 작은 값을 빠르게 찾아내는 완전 이진트리를 의미합니다.

 

이러한 형태의 완전 이진트리 자료구조에 Heap이라는 이름이 붙은 이유는 해당 단어가 차곡차곡 쌓아 올린 것을 의미하는데, 자료구조의 형태와 흡사하기 때문에 붙여진 이름입니다.

 

힙 특징

힙의 특징은 다음과 같습니다.

• 항상 완전 이진 트리 상태를 유지
• 중복 값을 허용
• 반 정렬 상태 (모든 노드들이 힙 종류에 따라 자식 노드보단 크거나 작지만, 형제 노드 간의 우선순위는 보장하지 못하는 상태)
• 부모 노드의 값은 항상 자식 노드들의 값보다 크거나 작음

 

힙 종류

최소 힙 (Min Heap)

Min Heap

부모의 값이 항상 자식들의 값보다 작거나 같은 힙을 최소 힙이라 합니다.

 

 

최대 힙 (Max Heap)

Max Heap

부모의 값이 항상 자식들의 값보다 크거나 같은 힙을 최대 힙이라 합니다.

 

 

힙 연산

힙은 다음과 같은 연산 처리 속도를 가지고 있습니다.

• 최대(최소) 값 탐색 : O(1)
• 데이터 삽입 , 삭제 : O(logN)

트리의 높이 만큼 타고 내려가면 데이터를 삽입하거나 삭제할 수 있으므로 O(logN)의 속도가 걸립니다.

 

아래의 삽입 ,삭제 예시는 최소 힙을 기준으로 작성되었습니다. 최대 힙도 동일합니다.

데이터 삽입

최소 힙 삽입

1. 트리의 가장 끝 위치에 데이터를 삽입합니다.
2. 데이터와 부모 노드의 값을 비교합니다.
   • 부모 노드의 값이 더 큰 경우, 부모 노드 자리와 교환합니다.
3. 힙 규칙에 맞을 때까지 2번 과정을 반복합니다.

 

데이터 삭제

최소 힙 삭제

1. 루트 노드를 반환 및 삭제합니다.
2. 루트 자리에 가장 마지막 노드를 올립니다.
3. 올린 노드와 자식 노드들을 비교합니다.
   • 부모 노드가 자식 노드 한 개보다 큰 경우, 자식노드와 교환합니다.
   • 부모 노드가 자식 노드 두 개보다 큰 경우, 두 자식 중 더 작은 노드와 교환합니다.
4. 힙 규칙에 맞을 때까지 3번 과정을 반복합니다.

 

 프로그래밍 언어로 구현

배열로 힙 구현

 

힙의 경우, 완전 이진 트리이기 때문에 배열로 구현하기 좋습니다. 

 

배열로 구현하면 해당 노드의 인덱스를 알면 깊이가 얼마인지, 부모와 자식노드가 어디인지 파악하기 쉽습니다.

 

다음과 같은 규칙을 알아두면 구현할 때 좋습니다.

• 부모 노드의 인덱스 : 자식 노드 인덱스 / 2
• 왼쪽 자식의 인덱스 : 2 * 부모 노드 인덱스
• 오른쪽 자식의 인덱스 : 2 * 부모 노드 인덱스 + 1

Java

import java.util.ArrayList;

/**
 * 최소 힙 기준으로 작성되었습니다.
 * 배열로 작성해도 좋지만, ArrayList를 사용해서 크기를 유동적으로 가져갈 수 있게 구현했습니다.
 */
public class Heap {

   ArrayList<Integer> heap;

   public Heap() {
      this.heap = new ArrayList<>();
      this.heap.add(0); // 1번부터 시작할 예정이므로 0 삽입
   }

   // 데이터 삽입
   public void push(int data) {

      // 1. 트리의 가장 끝 위치에 데이터 삽입
      heap.add(data);

      int dataIdx = heap.size() - 1; // 삽입한 데이터의 위치

      // 2. 부모 값과 비교 후, Heap 규칙에 맞지않으면 교환
      while (dataIdx > 1 && heap.get(dataIdx / 2) > data) {
         int parentVal = heap.get(dataIdx / 2);

         heap.set(dataIdx / 2, data);
         heap.set(dataIdx, parentVal);

         dataIdx /=  2;
      }
   }


   // 데이터 삭제
   public Integer pop() {
      // 힙이 비어있는 경우
      if (heap.size() == 1) {
         System.out.println("Heap is Empty");
         return null;
      }

      // 루트 노드 반환
      int returnVal = heap.get(1);

      // 1. 루트 자리에 마지막 노드를 올리고 마지막 노드 삭제
      heap.set(1, heap.remove(heap.size() - 1));

      int curIdx = 1;

      while (true) {

         int leftIdx = curIdx * 2;
         int rightIdx = curIdx * 2 + 1;

         int targetIdx = -1;

         if (rightIdx < heap.size()) { // 자식 노드가 둘인 경우
            targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx : rightIdx;
         } else if (leftIdx < heap.size()) { // 자식이 하나인 경우
            targetIdx = leftIdx;
         } else {
            break;
         }

         // 자식 노드와 부모 노드 값 비교
         if (heap.get(curIdx) <= heap.get(targetIdx)) {
            break;
         } else { // 부모 노드가 자식 노드보다 크다면 교환
            int parentVal = heap.get(curIdx);

            heap.set(curIdx, heap.get(targetIdx));
            heap.set(targetIdx, parentVal);

            curIdx = targetIdx; // 이동한 노드 인덱스 갱신
         }
      }

      return returnVal;
   }
}