힙 (Heap)

설명

간단하게 말하여, 힙은 우선순위 큐 입니다. JAVA에서는 PriorityQueue라는 구현체를 통해 Heap 자료구조를 사용할 수 있어요. 힙은 두 종류가 있는데 최대 힙과 최소 힙이 있어요. 최대 Heap(최소 Heap)은 단어와 같이 최대 값(최소 값)을 우선순위로 판단하여, 어떠한 값이 들어와도, 항상 같은 순서의 트리를 유지하며, 언제든지 최고 우선순위의 값을 적은 비용으로 쉽게 얻을수 있는 자료구조 입니다.

Heap의 속성 (성질)

• 최대 힙(또는 최소 힙)은 잎(leaf)의 계층을 제외한 모든 노드는 자식의 노드 보다 큰(또는 작은) 값을 가지고 있어야합니다.
• 왼쪽부터 차례대로 채워져있는 완전 이진 트리(Complete binary tree)이어야 합니다.
• 같은 계층의 노드들과는 정렬하지 않습니다.
• 루트(뿌리)노드로 부터 내려오는 위치의 노드들 오름차순(또는 내림차순)입니다

• 트리 A: 잎을 제외한 노드는 모두 정렬되었지만, 왼쪽부터 채워지지않아 Heap이 아닙니다.
• 트리 B: 왼쪽부터 채워졌지만, 2번노드의 값은 그 자식에값보다 작습니다. 따라서 Heap이 아닙니다.
• 트리 C: 잎을 제외한 모든 노드가 자식 또는 부모와 정렬 되어있고, 왼쪽부터 채워져있으므로 Heap입니다.

Heap을 만드는 방법

힙을 구성 하기 위해서는 다음의 순서대로 진행됩니다.

1. 순회를 시작할 힙이되는 마지막 노드⎣𝑛/₂⎦를 찾는다.
2. 마지막 노드 i를 이용해 자식노드가 있는지, 또한 있다면 그 중 자신 보다 큰값을 자신과 찾는다.
3. 찾은 값과 자신을 바꾸고 바꾼 자신의 위치는 그값의 자식이 되며, 자신보다 큰값이 나오지 않을때까지 반복한다.
4. 다음 노드(i -1)에서 다시 3.을 반복한다.

위 의 내용을 정리하면 아래와 같습니다.

• 최상위 노드(루트)가 가장 큰값이 되며, 위는 최대힙을 만드는 단계였습니다.
• 부모노드와 자식노드끼리는 순서의 값을 가지며, 항상 최대의 값을 가집니다.

Heap이 우선 값을 유지하는 방법

위에서는 완전이진트리로 힙을 어떻게 만드는지에 대해 알아봤습니다. 하지만, 힙은 언제나 새로운값이 들어와도 항상 우선 순위로 값을 관리합니다. 만약 저기서 더큰값이 추가된다면, 저 힙트리는 어떻게 바뀔까요? 새로운 값들을 추가해서 힙이 다시 어떻게 유지되는지 배워봅니다.

값 추가

힙트리에서 값을 추가 할때는 마지막 노드로 붙여주고 위에서 했던것과 동일하게 힙을 만들어 줍니다. 만약 새로운 값 17이 힙에 들어온다면 순서는 아래와 같이 바뀝니다.

구현 코드 (Java)

//== 힙(Heap) 을 만드는 메소드 ==//
public static void makeHeap(int arr[]) {
    // last heap
    int lh = arr.length / 2;
    System.out.println("Normal Array = " + Arrays.toString(arr));
    int eh = arr.length;
    while (lh-- > 0) {

        System.out.println("i: " + lh);
        pushDown(arr, lh, eh);
    }

    System.out.println("Array as Max Heap = " + Arrays.toString(arr));
}

public static void main(String args []) throws Exception {
    //== 힙 으로 만들기==//
    int array [] = {1, 5, 8, 2, 74, 9, 12, 104, 87, 43};
    Heap.makeHeap(array);
}