[자료 구조] 힙(Heap) in java

힙의 구조와 특징

 

완전 이진 트리 형태 [중복 값 허용, 반 정렬 상태]로 최소값 또는 최대값을 빠르게 찾아내는데 유용한 자료구조입니다.

따라서 최소 힙, 최대 힙 두가지 종류가 존재합니다.

+ 우선순위 큐(Priority Queue)를 위한 자료구조라고도 합니다.

최소 힙(Min Heap)

 

부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태 -> 즉, root 노드가 가장 작습니다.

자식 노드에서는 따로 규칙이 없어서 왼쪽이 오른쪽보다 클수도, 오른쪽이 왼쪽보다 클 수도 있습니다.. 보장되어있지 않아 반 정렬 형태라고 합니다.

최대 힙(Max Heap)

ㅗ

부모 노드의 키가 자식노드의 키보다 크거나 같은 형태 -> 즉, root 노드가 가장 큽니다.

최소 힙과 마찬가지로 반 정렬 형태입니다.

힙의 시간 복잡도

평균 O(logN) 복잡도를 가집니다.

 

힙의 삽입

최소 힙의 삽입

트리의 가장 끝 위치에 데이터 삽입, 부모 노드와 키 비교한 후 작을 경우 부모 자리와 교체합니다. 이 과정을 반복합니다.

 

최대 힙의 삽입 

트리의 가장 끝 위치에 데이터 삽입, 부모 노드와 키 비교한 후 클 경우 부모 자리와 교체합니다. 이 과정을 반복합니다.

 

힙의 삭제

최소 힙의 삭제

최상위 노드 반환 및 삭제 한 다음, 가장 마지막 위치의 노드를 최상위 노드로 위치 시킵니다.

자식 노드 중 작은 값과 비교 후 부모 노드보다 작으면 자리를 교체합니다. 이 과정을 반복합니다.

- 그림은 생략하겠습니다.

 

최대 힙의 삭제 

최상위 노드 반환 및 삭제 한 다음, 가장 마지막 위치의 노드를 최상위 노드로 위치 시킵니다.

자식 노드 중 큰 값과 비교 후 부모 노드보다 크면 자리를 교체합니다. 이 과정을 반복합니다.

- 그림은 생략하겠습니다.

힙의 구현

힙은 보통 배열으로 구현됩니다. 인덱스로 접근하는 것이 최대, 최소값을 비교하면서 반복적으로 정렬하기 편하기 때문입니다.

index = 0은 그냥 더미값으로 채워놓고 항상 index = 1 부터 root 노드가 시작한다는 것만 아시면 됩니다.

이때 항상 변하지 않는 index 규칙이 있습니다.

자식 노드 (왼쪽) : (부모노드 인덱스 값) *2
자식 노드 (오른쪽) : (부모노드 인덱스 값) *2 + 1
부모 노드 : (자식노드 인덱스 값)/2

위의 index 규칙만 안다면 배열로 힙 구현하는 것은 쉽습니다.

 

ArrayList로 최소 힙 구현

package com.lecture.비선형자료구조.Heap;
// 최소 힙 구현
import java.util.ArrayList;

class MinHeap{
    ArrayList<Integer> heap;

    public MinHeap(){
        this.heap = new ArrayList<>();
        this.heap.add(0);
    }

    public void insert(int data){
        heap.add(data);

        int cur = heap.size() - 1;
        while( cur > 1 && heap.get(cur/2)> heap.get(cur)){
            int parentVal = heap.get(cur / 2);
            heap.set(cur / 2, data);
            heap.set(cur, parentVal);

            cur /= 2;
        }
    }

    public Integer delete(){
        if(heap.size() ==1){
            System.out.println("Heap is empty");
            return null;
        }

        int target = heap.get(1);

        heap.set(1, heap.get(heap.size() -1));
        heap.remove(heap.size() -1);

        int cur = 1; // 최상위 노드로 위치시킴
        while(true){
            int leftIdx = cur*2;
            int rightIdx = cur*2 +1;
            int targetIdx = -1;

            if(rightIdx < heap.size()){ // 자식 노드가 두개 있을 경우
                targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx:rightIdx;
            } else if (leftIdx < heap.size()){ // 자식 노드가 한개 있을 경우
                targetIdx = cur*2;
            } else {
                break; // 자식노드가 없을 경우
            }

            if(heap.get(cur)< heap.get(targetIdx)){
                break;
            }else {
                int parentVal = heap.get(cur);
                heap.set(cur, heap.get(targetIdx));
                heap.set(targetIdx, parentVal);
                cur = targetIdx; // 아래로 내려가면서 계속 반복
            }
        }

        return target;
    }
    public void printTree(){
        for (int i = 1; i < this.heap.size(); i++) {
            System.out.print(this.heap.get(i)+ " ");
        }
        System.out.println();
    }
}
public class Main {
    public static void main(String[] args) {

        MinHeap minHeap = new MinHeap();
        System.out.println("== 데이터 삽입 ==");
        minHeap.insert(30);
        minHeap.insert(40);
        minHeap.insert(10);
        minHeap.printTree();
        minHeap.insert(50);
        minHeap.insert(60);
        minHeap.insert(70);
        minHeap.printTree();
        minHeap.insert(20);
        minHeap.printTree();
        minHeap.insert(30);
        minHeap.printTree();
        minHeap.insert(30);

        System.out.println();
        System.out.println("== 데이터 삭제 ==");
        System.out.println("삭제: "+ minHeap.delete());
        minHeap.printTree();
        System.out.println("삭제: "+ minHeap.delete());
        minHeap.printTree();
        System.out.println("삭제: "+ minHeap.delete());
        minHeap.printTree();
    }
}

== 데이터 삽입 ==
10 40 30 
10 40 30 50 60 70 
10 40 20 50 60 70 30 
10 30 20 40 60 70 30 50 

== 데이터 삭제 ==
삭제: 10
20 30 30 30 60 70 40 50 
삭제: 20
30 30 40 30 60 70 50 
삭제: 30
30 30 40 50 60 70

 

ArrayList로 최대 힙 구현

위의 최소 힙에서 부등호만 바꾸면 최대힙이 됩니다. 결과는 아래와 같습니다.

== 데이터 삽입 ==
40 30 10 
70 50 60 30 40 10 
70 50 60 30 40 10 20 
70 50 60 30 40 10 20 30 

== 데이터 삭제 ==
삭제: 70
60 50 30 30 40 10 20 30 
삭제: 60
50 40 30 30 30 10 20 
삭제: 50
40 30 30 30 20 10

 

참고할 만한 문제 :

https://www.acmicpc.net/problem/24174 

24174번: 알고리즘 수업 - 힙 정렬 2

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스