힙(Heap)

힙(Heap) 이란?

완전 이진트리의 일종으로 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

최대힙

각 노드의 키 값이 그 자식노드의 키 값보다 크거나 같은 자료구조, 따라서 루트는 모든 자식노드보다 크거나 같다.

최소힙

각 노드의 키 값이 그 자식노드의 키 값보다 작거나 같은 자료구조, 따라서 루트는 모든 자식노드보다 작거나 같다.

힙(Heap) 연산

• 최소힙을 기준으로 설명하였습니다.
• 최대힙의 경우 똑같은 원리이지만 부등호 방향만 바뀐다고 생각하면 됩니다.

삽입(insert)

1. 삽입할 원소를 Heap의 마지막 index에 추가한다.
   
   
2. 삽입한 노드의 부모 노드를 찾는다.
   
   
3. 부모의 값과 비교하여 부모 노드의 값 보다 작다면 부모노드와 위치를 바꾼다.
   
   
4. 부모 노드보다 값이 크거나 루트 노드에 도달할 때 까지 2번과 3번을 반복한다. (최소 힙의 성질을 만족할 때 까지 반복한다.)

삭제(delete)

Heap에서 삭제 연산은 루트 노드를 삭제하고 삭제한 값을 반환하는 연산을 말한다.

1. 루트 노드를 삭제한다.
   
   
2. 마지막 노드(n이라고 부르겠다)를 루트 노드로 이동시킨다.
   
   
3. n의 두 자식노드 중에서 더 작은 자식노드와 비교하여 n보다 작을 경우 자리를 바꾼다.
   
   
4. 자식 노드값이 더 크거나 자식노드가 없을 때 까지 3번을 반복한다. (최소 힙의 성질을 만족할 때 까지 반복한다.)

최소힙 구현 코드

🤚 참고사항

• Java를 사용하여 구현하였습니다.
• List를 사용하여 구현하였습니다.

Class MinHeap {
    ArrayList<Integer> heap = new ArrayList<>();
    
    public void insert(int n) {
        heap.add(n);
        int pos = heap.size() - 1;
        int parent = (pos - 1) / 2;
        
        // 부모 노드가 없거나 최소힙 조건을 만족할 때 까지 swap
        while(pos > 0 && heap.get(parent) > heap.get(pos) {
            int tmp = heap.get(parent);
            heap.set(parent, heap.get(pos));
            heap.set(pos, tmp);
            
            pos = parent;
            parent = (pos - 1) / 2;
        }
    }
    
    public int delete() {
        if(heap.isEmpty()) {
            System.out.println("Empty!!");
            return -1;
        }
        
        int deleteValue = heap.get(0);
        
        heap.set(0, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);
        
        int pos = 0;
        int leftChild = (pos + 1) * 2 - 1;
        int rightChild = (pos + 1) * 2;
        
        // 자식 노드가 없거나 최소힙 조건을 만족할 때 까지 swap
        while(heap.size() - 1 >= leftChild) {
            int min = heap.get(leftChild);
            int minPos = leftChild;
            
            // 자식노드 중에 더 작은값 찾기
            if(heap.size() - 1 >= rightChild && min > heap.get(rightChild) {
                min = heap.get(rightChild);
                minPos = rightChild;
            }
            
            if(heap.get(pos) < min) break;
            
            int tmp = heap.get(pos);
            heap.set(pos, heap.get(minPos));
            heap.set(minPos, tmp);
            
            pos = minPos;
            lefetChild = (pos + 1) * 2 - 1;
            rightChild = (pos + 1) * 2;
        }
        
        return deleteValue;
    }
}

시간복잡도

👉 O(logN)

삽입연산, 삭제연산 모두 힙의 높이만큼 swap 연산을 한다.
힙은 완전 이진트리이므로 높이는 logN 이다. 따라서 시간복잡도 또한 O(logN) 이다.