[알고리즘] 힙(heap) 자료구조

힙이란?

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리

 

우선순위 큐를 위해 만들어진 자료구조이다.

 

 

 

이진 트리

한 노드가 최대 두개의 노드를 자식으로 가질 수 있는 트리

마지막 레벨을 제외한 모든 레벨에는 노드들이 가득차있고, 마지막 레벨의 노드들돠 좌측부터 순서로 들어가있는 형태의 이진트리를 완전 이진 트리라고 한다. 

 

 

우선순위 큐

큐: FIFO 형식의 자료구조

우선순위 큐는 큐에 우선순위라는 개념을 접목시킨 자료구조이다.

우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

 

 

힙

힙: 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조

부모 노드의 키 값이 자식 노드의 키 값보다 항상 큼/ 작음

이진 탐색 트리와 달리 중복된 값이 허용된다. 

가장 크거나 작은 값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조라고 할 수 있다.

 

 

1. 최대 힙 (max heap)

• 부모 노드의 키값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 부모 노드 >= 자식 노드

 

가장 큰 값인 루트를 꺼내는 작업을 반복하고, 그 ㄱ

 

 

2. 최소 힙 (min heap)

- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

- 부모 노드 <= 자식 노드

 

 

최소 힙에 저장할 때

A) 들어올 새 노드를 우선순위가 가장 낮다는 가정을 하고 맨 끝 위치에 저장

B) 부모 노드와 우선 순위를 비교해서 위치가 바뀌어야 하면 바꾼다.

C) 올바르게 위치할 떄까지 B 반복

 

 

 

최소 힙에서 삭제할 때

우선 순위 큐에서 pop 할 떄는 가장 우선순위가 높은 데이터를 빼낸다.

A) 루트 노드를 반환(삭제)하고 마지막 노드(가장 최 하단부)를 루트 노드 자리에 옮긴다.

B) n의 왼쪽, 오른쪽 자식노드 중 더 우선순위가 높은 것과 비료를 진행한다.

C) 최소 힙의 구조를 유지할 떄까지 B 반복

 

 

 

 

 

힙에서의 부모 자식 관계

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

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

부모의 인덱스 = (자식의 인덱스) / 2

 

 

java ArrayList를 이용해서 최소 힙을 구현할 수 있다.

 

import java.util.ArrayList;

public class minHeap {
    private ArrayList<Integer> heap;

    public minHeap() {
        heap = new ArrayList<Integer>();
        heap.add(0); // 0번째 인덱스는 사용하지 않음
    }

    public void insert(int number) {
        heap.add(number);
        int p = heap.size() - 1; // 새로 삽입한 노드의 인덱스
        while (p > 1 && heap.get(p / 2) > heap.get(p)) {
            // 부모가 자식보다 크다면?
            int tmp = heap.get(p / 2);
            heap.set(p / 2, number);
            heap.set(p, tmp);

            p /= 2; //인덱스 부모 노드 인덱스 값으로 변경
        }
    }

    public int delete() {
        if (heap.size() - 1 < 1) {
            return 0;
        }

        int deleteItem = heap.get(1); // 루트 노드 삭제
        heap.set(1, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        int index = 1; // 루트 노드 인덱스

        while ((index * 2) < heap.size()) {
            int min = heap.get(index * 2); //왼쪽 자식 인덱스 값
            int minIndex = index * 2;

            if (((index * 2 + 1) < heap.size()) && min > heap.get(index * 2 + 1)) {
                min = heap.get(index * 2 + 1);
                minIndex = index * 2 + 1;
            }

            if (min > heap.get(index)) { // 부모가 더 작은 경우
                break;
            }

            int tmp = heap.get(index);
            heap.set(index, heap.get(minIndex));
            heap.set(minIndex, tmp);
            index = minIndex;
        }
        return deleteItem;


    }
}