[자료구조] 힙(Heap)

 

 

 

 

 

 

 

 

자료구조, 힙(Heap)에 대해 알아보기

---

 

 

 

Heap의 구조와 특징 

 

힙이란 완전이진트리를 기반으로 하는 자료구조입니다.

• 노드의 값이 자식 노드 값보다 크거나 같음 (최대힙)
• 노드의 값이 자식 노드 값보다 작거나 같음 (최소힙)
• 우선순위 큐를 구현하는데 적합
• 최대 값이나 최소 값을 빠르게 찾음
• 중간값을 조정하면서 구조 유지 가능 

 

 

 

Heap의 종류

 

1. 최대힙(MaxHeap)

 

최대힙이란 모든 부모 노드가 자신의 자식 노드보다 크거나 같은 형태를 말합니다. 

 

최대힙에서 루트 노드는 트리 전체에서 가장 큰 값을 갖습니다. 

 

 

최대힙 예시

 

2. 최소힙(MinHeap)

 

최소힙이란 모든 부모 노드가 자신의 자식 노드보다 작거나 같은 형태를 말합니다. 

 

최소힙에서 루트 노드는 트리 전체에서 가장 작은 값을 갖습니다. 

 

 

최소힙 예시

 

 

Heap의 연산

 

1. 삽입(Insert) 

 

새로운 요소를 힙에 추가합니다. 힙의 마지막 노드에 요소를 추가한 후 힙의 조건을 만족 시키기 위해 부모 노드와 비교하며 위치를 조정합니다. 

 

2. 삭제(Delete)

 

기존에 있던 요소를 제거합니다. 힙의 마지막 요소를 루트로 이동시키고 힙의 조건을 만족 시키기 위해 자식 노드와 비교하며 위치를 조정합니다. 

 

3. 정렬(Heapify)

 

주어진 데이터 집합 전체를 힙 구조에 맞게 재정렬합니다. 

 

 

Heap의 시간복잡도

• 삽입 연산 : O(log n) 
• 삭제 연산 : O(log n)
• 힙 정렬 : O(log n)

 

 

JAVA로 Heap 구현 

 

public class MinHeap{
    private int[] Heap;
    private int size;
    private int maxsize;

    public MinHeap(int maxsize){
        this.maxsize = maxsize;
        this.size = 0;
        Heap = new int[this.maxsize + 1];
        Heap[0] = Integer.MIN_VALUE;
    }

    private int parent(int pos) { return pos / 2; }              //부모노드 위치 반환
    private int leftChild(int pos) { return (2 * pos); }        //왼쪽 자식노드 위치 반환
    private int rightChild(int pos) { return (2 * pos) + 1; }  //오른쪽 자식노드 위치 반환

    private boolean isLeaf(int pos){
        if (pos > (size / 2) && pos <= size){ 
            return true;
        }
        return false;
    }

    private void swap(int fpos, int spos){
        int tmp;
        tmp = Heap[fpos];
        Heap[fpos] = Heap[spos];
        Heap[spos] = tmp;
    }

    public void insert(int element){
        if (size >= maxsize) {
            return;
        }
        Heap[++size] = element;
        int current = size;

        while (Heap[current] < Heap[parent(current)]){
            swap(current, parent(current));
            current = parent(current);
        }
    }

    public void minHeapify(int pos){
        if (!isLeaf(pos)) {
            if (Heap[pos] > Heap[leftChild(pos)] || Heap[pos] > Heap[rightChild(pos)]) {
                if (Heap[leftChild(pos)] < Heap[rightChild(pos)]) {
                    swap(pos, leftChild(pos));
                    minHeapify(leftChild(pos));
                }
                else {
                    swap(pos, rightChild(pos));
                    minHeapify(rightChild(pos));
                }
            }
        }
    }

    public int remove(){
        int popped = Heap[1];
        Heap[1] = Heap[size--];
        minHeapify(1);
        return popped;
    }
}