힙(Heap)과 완전이진트리(Complete Binary Tree)

완전이진트리(Complete Binary Tree)란?

• 완전이진트리는 이진트리의 일종으로 최대 2개의 자식노드를 가질 수 있다.
• 마지막 레벨을 제외한 모든 레벨이 꽉 차있어야 한다.
• 마지막 레벨은 왼쪽부터 채워져 있어야 한다.

완전 이진트리의 예

올바른 예	틀린 예
마지막 레벨을 제외한 모든 레벨이 꽉 채워져 있음. 마지막 레벨은 왼쪽부터 채워져 있음.	마지막 레벨을 제외한 모든 레벨이 꽉 채워져 있음. 하지만 노드 2의 오른쪽 자식이 비워져있음.

 

 

완전이진트리 특성

1. 노드의 개수:
   레벨 h에 있는 노드의 최대 개수는 2^h이다.
   예를 들어, 루트 레벨(레벨 0)에는 최대 1개의 노드가 있고, 레벨 1에는 최대 2개의 노드, 레벨 2에는 최대 4개의 노드가 있을 수 있다.
2. 트리의 높이:
   노드의 개수가 n인 완전 이진 트리의 높이는 ⌊log⁡2(n)⌋이다.
3. 노드의 인덱스:
   배열로 표현된 완전 이진 트리에서 노드의 인덱스는 다음과 같이 계산된다
   • 부모 노드 인덱스: (i−1)/2
   • 왼쪽 자식 노드 인덱스: 2i+1
   • 오른쪽 자식 노드 인덱스: 2i+2

 

 

 

힙(Heap)이란?

힙(Heap)은 이진 트리 기반의 완전 이진 트리(Complete Binary Tree) 자료구조로, 특정한 조건을 만족하는 노드 간의 우선순위를 가지는 트리이다. 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용되며, 힙 정렬(Heap Sort) 알고리즘의 기초가 된다.

 

힙의 종류

 

• 최대 힙(Max Heap):
  • 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같다.
  • 루트 노드는 힙의 최대값이 됩니다.

 

• 최소 힙(Min Heap):
  • 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같다.
  • 루트 노드는 힙의 최소값이 됩니다.

 

 

 

 

 

힙(Heap)의 특성

 

• 완전 이진 트리(Complete Binary Tree)
  힙은 완전 이진 트리 구조를 갖는다.
  트리가 왼쪽부터 채워지며 마지막 레벨이 왼쪽에서 오른쪽으로 채워지는 것을 의미한다.
• 힙 속성(Heap Property)
  최대 힙의 경우, 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 한다.
  최소 힙의 경우, 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 한다.

 

 

 

힙의 연산

삽입 (Insert)

1. 트리의 마지막 위치에 새로운 요소를 추가.
2. 힙 속성을 만족할 때까지 새로운 요소를 상향 이동(부모와 교환).

아래 이미지는 새로운 요소 7을 삽입하는 과정이다.

 

삽입 연산 Java로 구현

import java.util.ArrayList;
import java.util.List;

public class MaxHeap {
    private List<Integer> heap;

    public MaxHeap() {
        heap = new ArrayList<>();
    }

    // 삽입 연산
    public void insert(int value) {
        // 새로운 값을 힙의 마지막 위치에 추가
        heap.add(value);
        // 현재 노드의 인덱스
        int current = heap.size() - 1;
        
        // 힙 속성을 만족하도록 상향 이동
        while (current > 0) {
            // 부모 노드의 인덱스 계산
            int parent = (current - 1) / 2;
            // 현재 노드의 값이 부모 노드의 값보다 크면 교환
            if (heap.get(current) <= heap.get(parent)) {
                break;
            }
            swap(current, parent);
            // 상향 이동 후 현재 노드를 부모 노드로 업데이트
            current = parent;
        }
    }

    // 두 인덱스의 값을 교환하는 메서드
    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
}

 

 

 

 

삭제 (Delete)

1. 트리의 마지막 노드 값을 루트 위치로 이동.
2. 트리의 마지막 노드는 제거.
3. 힙 속성을 유지하기 위해 새로운 루트 노드를 하향 이동(자식과 교환).

 

 

삭제 연산 Java로 구현

import java.util.NoSuchElementException;

public class MaxHeap {
    private List<Integer> heap;

    public MaxHeap() {
        heap = new ArrayList<>();
    }

    // 최댓값(루트 노드)을 삭제하는 연산
    public int remove() {
        // 힙이 비어 있는 경우 예외 처리
        if (heap.size() == 0) {
            throw new NoSuchElementException();
        }
        
        // 루트 노드의 값 저장 (최댓값)
        int removedValue = heap.get(0);
        // 힙의 마지막 노드를 가져와 루트 노드 위치에 설정
        int lastValue = heap.remove(heap.size() - 1);
        
        if (heap.size() > 0) {
            heap.set(0, lastValue);
            // 힙 속성을 만족하도록 하향 이동
            heapifyDown(0);
        }
        
        // 제거된 최댓값 반환
        return removedValue;
    }

    // 하향 이동을 통해 힙 속성을 유지하는 메서드
    private void heapifyDown(int current) {
        // 현재 노드의 왼쪽 자식 노드 인덱스
        int leftChild = 2 * current + 1;
        // 현재 노드의 오른쪽 자식 노드 인덱스
        int rightChild = 2 * current + 2;
        // 최대값을 가진 노드의 인덱스를 현재 노드로 초기화
        int largest = current;
        
        // 왼쪽 자식이 현재 노드보다 크면 largest 업데이트
        if (leftChild < heap.size() && heap.get(leftChild) > heap.get(largest)) {
            largest = leftChild;
        }
        // 오른쪽 자식이 현재 노드보다 크면 largest 업데이트
        if (rightChild < heap.size() && heap.get(rightChild) > heap.get(largest)) {
            largest = rightChild;
        }
        
        // 현재 노드가 최대값 노드가 아니면 교환 후 재귀적으로 하향 이동
        if (largest != current) {
            swap(current, largest);
            heapifyDown(largest);
        }
    }

    // 두 인덱스의 값을 교환하는 메서드
    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
}