[자료구조] 비선형 자료구조 3탄 : 힙 트리, 우선순위 큐

 

 

 

1. 힙 트리란

힙(heap)은 차곡차곡 쌓아올린 더미란 뜻을 지닌다. 힙 트리는 완전 이진 트리로, 부모의 값은 항상 자식들보다 크거나 작거나하는 성질을 가진다. 부모의 값이 자식들의 값보다 클 때에는 최대 힙 (Max heap), 작을 때에는 최소 힙 (Min heap)이라고 한다. 루트 노드에는 항상 가장 크거나 작은 값이 들어가기 때문에 트리의 최댓값(최솟값)을 찾을 때에는 O(1)이 걸린다. 또한 삽입 및 삭제는 O(logN)이 걸린다.

 

 

📌 우선순위 큐 (PriorityQueue)

들어간 순서에 상관 없이 우선순위가 높은 데이터를 꺼낼 수 있는 큐를 우선순위 큐라고 한다. 보통 힙트리를 이용하여 구현할 수 있다. 그렇기 때문에 우선순위 큐의 시간복잡도는 삽입,삭제 O(logN)이 걸린다. 값을 꺼낼 때에는 마찬가지로 O(1)이다. 

 

 

📌  데이터의 삽입 (O(logN))

 

 

1. 가장 끝의 자리에 노드를 삽입한다.
2. 그 노드와 부모 노드를 서로 비교한다.
3. 규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다. (부모노드의 인덱스 = 자식노드의 인덱스/2)
4. 규칙에 맞을 때까지 3번 과정을 반복한다.

 

📌  데이터의 삭제 (O(logN))

 

 

1. 루트 노드를 제거한다. (최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다.)
2. 루트 자리에 가장 마지막 노드를 삽입한다.
3. 올라간 노드와 그의 자식 노드(들)와 비교한다.
4. 조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다.

• 최대 힙
  1. 부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.
  2. 부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.
  3. 부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다.

• 최소 힙
  1. 부모보다 더 작은 자식이 없으면 교환하지 않고 끝낸다.
  2. 부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환하면 된다.
  3. 부모보다 더 작은 자식이 둘 있으면 자식들 중 작은 값과 교환한다.

5. 조건을 만족할 때까지 4의 과정을 반복한다.

 

 

2. 힙 트리의 구현 (java)

힙은 완전 이진 트리이므로 중간에 비어있는 인덱스가 없기 때문에 int 배열로 구현하는 것이 일반적이다. 

먼저 힙을 인터페이스로 구현하여 구조를 잡았다. 

 

public interface Heap {
    void insert(int x); //삽입
    int delete(); //최솟값/최댓값 삭제
    int get(); //최솟값/최댓값 얻기
}

 

📝 최소 힙 

public class MinHeapImpl implements Heap {
    int[] heap;
    int index; //가장 밑에 있는 노드의 인덱스.
    @Override
    public void insert(int x) {
        heap[++index] = x;
        int idx = index;
        while (idx != 1) {
            int parent = idx/2;
            if (heap[parent] <= heap[idx]) break; //부모보다 자식이 크면 맞는 힙.
            swap(parent, idx);
            idx = parent;
        }
    }

    @Override
    public int delete() { //삭제하면서 최솟값 반환.
        if (index == 0) return 0;

        int res = heap[1];
        heap[1] = heap[index--];
        int idx = 1;
        while (idx*2 <= index) {
            int lc = 2*idx, rc = 2*idx+1;
            int min_child = (rc <= index && heap[lc] > heap[rc] ? rc : lc);
            if (heap[idx] <= heap[min_child]) break;
            swap(idx, min_child);
            idx = min_child;
        }
        return res;

    }
    @Override
    public int get() {
        if (index == 0) return -1;
        return heap[1];
    }
    public void swap(int x, int y) {
        int tmp = heap[x];
        heap[x] = heap[y];
        heap[y] = tmp;
    }

    public MinHeapImpl() {
        heap = new int[100001];
        index = 0;
    }
}

 

📝 최대 힙 

public class MaxHeapImpl implements Heap {
    int[] heap;
    int index; //가장 밑에 있는 노드의 인덱스.
    @Override
    public void insert(int x) {
        heap[++index] = x;
        int idx = index;
        while (idx != 1) {
            int parent = idx/2;
            if (heap[parent] >= heap[idx]) break; //부모보다 자식이 작으면 맞는 힙.
            swap(parent, idx);
            idx = parent;
        }
    }

    @Override
    public int delete() { //삭제하면서 최댓값 반환.
        if (index == 0) return 0;

        int res = heap[1];
        heap[1] = heap[index--];
        int idx = 1;
        while (idx*2 <= index) {
            int lc = 2*idx, rc = 2*idx+1;
            int min_child = (rc <= index && heap[lc] < heap[rc] ? rc : lc);
            if (heap[idx] >= heap[min_child]) break;
            swap(idx, min_child);
            idx = min_child;
        }
        return res;

    }
    @Override
    public int get() {
        if (index == 0) return -1;
        return heap[1];
    }
    public void swap(int x, int y) {
        int tmp = heap[x];
        heap[x] = heap[y];
        heap[y] = tmp;
    }

    public MaxHeapImpl() {
        heap = new int[100001];
        index = 0;
    }
}

 

📝 Test Code

public class HeapTest {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        Heap maxHeap = new MaxHeapImpl();
        Heap minHeap = new MinHeapImpl();
        for (int i = 0; i < 5; i++) {
            int x = Integer.parseInt(br.readLine());
            maxHeap.insert(x);
            minHeap.insert(x);
        }

        sb.append("= max heap =\n");
        while (maxHeap.get() != -1) {
            sb.append(maxHeap.delete()+" ");
        }
        sb.append("\n= min heap =\n");
        while (minHeap.get() != -1) {
            sb.append(minHeap.delete()+" ");
        }
        System.out.println(sb);
    }
}