[자료구조] 힙

우선순위 큐란?

우선순위의 개념을 큐에 도입한 자료 구조
데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.
우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다.

힙이란? 

완전이진트리 구조
최댓값과 최솟값을 뽑아낼 때 사용하기 좋은 자료구조이다. 
힙은 완전히 정렬된 상태를 유지하는 것이 아닌 Level에 따른 정렬만 이루어져 느슨한 정렬상태를 유지한다. 
(Max Heap인 경우 부모가 자식보다 큰 값을 가지고 있고, Min Heap인 경우 부모가 자식보다 작은 값을 가지고 있어야 함) 

힙의 종류 

Max Heap

1. 루트 노드에는 항상 가장 큰 값이 위치하고 있으며, 부모 노드가 자식 노드들보다 무조건 값이 커야한다. 

Min Heap

1. 루트 노드에는 항상 가장 작은 값이 위치하고 있으며, 부모 노드가 자식 노드들보다 무조건 값이 작아야한다.

힙의 구현 

1. 힙은 보통 배열을 이용하여 구현하며, 부모 노드와 자식 노드를 구분하는 방식은 다음과 같다. 
2. 부모의 인덱스를 i라고 했을때 왼쪽 자식의 인덱스는 2 * i, 오른쪽 자식의 인덱스는 2 * i + 1 이다.

힙의 삽입 연산

1. 가장 마지막 위치에 삽입할 데이터를 삽입한다.
2. 힙의 특성에 맞게 데이터들의 위치를 조정한다.

힙의 삭제 연산 

1. 루트 노드를 제거 한다.
2. 마지막 노드를 루트 노드의 위치로 옮긴다.
3. 힙의 특성에 맞게 데이터들의 위치를 조정한다.

 

자바를 이용한 구현

    public void insert(int n) {
        heap[++heapSize] = n;
        int parent = heapSize/2;
        int child = heapSize;
        while(child >= 2 && heap[parent] < heap[child]) {
            SWAP(parent, child);
            child = parent;
            parent = child/2;
        }
    }

    public int delete() {
        int data = heap[1];
        heap[1] = heap[heapSize--];
        int parent = 1;
        int child = 2;
        while(child <= heapSize && heap[parent] < heap[child]) {
            SWAP(parent, child);
            parent = child;
            child = heap[heap[parent * 2] < heap[parent * 2 + 1] ? parent * 2 + 1 : parent * 2];
        }
        return data;
    }

 

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

https://aerocode.net/193

우선순위 큐 ADT