[알고리즘] 힙 (Heap)

힙 (Heap)

1. 힙의 개념

힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다.

부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(혹은 작은) 이진 트리를 말한다.

힙은 이진트리기 때문에 배열을 사용해 나타낼 수 있다.

🎨 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2

🎨 오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1

🎨 부모의 인덱스 = 자식의 인덱스 / 2


2. 힙의 삽입 연산

  1. 힙의 끝에 새로운 노드를 삽입한다.

  2. 삽입된 노드와 그 부모 노드의 키 값을 비교한다.

  3. 노드의 키 값이 부모 노드의 키 값보다 작으면 두 노드의 위치를 바꾼다.
  4. 삽입된 노드의 키 값이 자신의 부모 노드 키 값보다 커질 때까지 2, 3의 과정을 반복한다.


// 최소 힙을 예시로
ArrayList<Integer> heap;

void insert(int input) {
    heap.add(input);
    int position = heap.size() - 1;
    while (position > 1 && heap.get(position / 2) < heap.get(position)) {
        int tmp = heap.get(position / 2);
        heap.set(position / 2, heap.get(position));
        heap.set(position, temp);
        position /= 2;
    }
}


3. 힙의 삭제 연산

  1. 최소 힙에서의 삭제 연산은 루트 노드를 삭제하는 것이다.
  2. 말단 노드를 루트 노드로 옮긴다.
  3. 자식 값과 비교해 최소 힙 특성을 만족시킨다.
  4. 부모 노드 키 값이 현재 노드 키 값보다 작을 때 까지 반복한다.
void delete() {
	if (heap.size() - 1 < 1) {
        return 0;
    }
    int deleteData = heap.get(1);
    heap.set(1, heap.get(heap.size() - 1));
    heap.remove(heap.size() - 1);
    int position = 1;
    
    while ((position * 2) < heap.size()) {
        int min = heap.get(position * 2);
        int minPos = position * 2;
        
        if (((position * 2 + 1) < heap.size()) && min > heap.get(position * 2 + 1)) {
            min = heap.get(position * 2 + 1);
            minPos = position * 2 + 1;
        }
        
        if (heap.get(position) < min) {
            break;
        }
        
        int tmp = heap.get(position);
        heap.set(position, heap.get(minPos));
        heap.set(minPos, tmp);
        position = minPos;
    }
    return deleteData;
}



힙 정렬은 여기에!