Heap

이진트리 형태의 자료 구조입니다. 최대값 혹은 최소값을 빠르게 찾기 위해 주로 사용합니다.
이 글에서는 최대힙을 기준으로 설명합니다.

코드가 깔끔하지 않을 수 있음 주의 

 

힙 자료구조는 두가지 형태가 있습니다. 

 

최대힙은 아래 그림 처럼 부모 노드가 반드시 자식 노드 보다 커야합니다. 

최소힙은 아래 그림과는 정 반대로 부모 노드가 반드시 자식 노드보다 작아야 합니다.

 

최대힙과 최소힙은 사용하는 사람이 필요에 따라 선택하면 됩니다. 기본적인 원리는 최대/최소 모두 같습니다.

 

 

Heap 자료구조

 

 

특징 / 삽입 / 삭제

Heap도 데이터를 저장하기 위한 자료구조 이기 때문에 삽입과 삭제가 필요합니다. 이제부터 해당 글은 최대힙을 기준으로 설명합니다.

 

특징

Heap 자료구조는 주로 배열 혹은 리스트로 이를 표현합니다. JAVA 에서 아래와 같은 형태로 데이터를 저장할 수 있는데 이는 위 그림을 리스트로 나타낸 모습입니다.

ArrayList<Integer> heap = new ArrayList<>();
heap.add(null); 
heap.add(100)
heap.add(94)
heap.add(99)
heap.add(77)
heap.add(93)
heap.add(98)

// heap: {null,100,94,99,77,93,98}

 

Heap 자료 구조는 몇가지 특징이 있는데 아래와 같습니다.

• 부모노드의 인덱스: 자식노드의 인덱스 / 2
• 자식노드의 인덱스: 부모노드의 인덱스 * 2
• 오른쪽 자식 노드의 인덱스: 부모노드의 인덱스 * 2 + 1

해당 리스트에서 0번 인덱스에는 null이 들어가있는데 계산 편의를 위해 실제 데이터는 인덱스 1부터 시작하도록 하기 위함입니다.

0 부터 시작하면 추가로 1을 더해줘야 해서 헷갈리고 보기도 안좋습니다.

 

위 그림에서 100이라는 숫자는 root 노드 자리에 위치하고 있습니다.

root 노드는 리스트에서 1 이라는 인덱스에 위치하고 있습니다.

 

왼쪽 자식 노드에 접근 하고 싶을 때 위에서 말한 부모노드의 인덱스  * 2 공식에 실제 숫자를 대입 해보면 1 * 2 라는 식이 나옵니다.

즉 인덱스 2에 왼쪽 자식 노드가 있다는 의미 입니다. 인덱스 2는 94라는 데이터를 가지고 있습니다.

 

그림과 비교해보면 정상적으로 데이터가 들어가있는 것을 확인 할 수 있습니다.

 

반대로 인덱스 2에서 부모 노드에 접근 하고 싶다면 자식노드의 인덱스 / 2 공식을 사용할 수 있습니다.

인덱스 2는 root가 아니기에 누군가의 자식 노드 입니다. 2 / 2 라는 식이 나오는데 1이라는 결과를 토대로 리스트의 인덱스 1로 접근해보면 100 이라는 숫자가 나옵니다.

 

 

삽입

Heap 자료구조에서는 데이터를 추가하면 해당 데이터를 다시 힙 구조로 바꿔주어야 합니다. 들어온 데이터가 부모 노드 보다 작은지 큰지 체크하고 다시 이를 정렬하는 과정이 필요합니다.

 

앞이나 뒤 원하는 곳에 데이터를 추가하고 다시 힙 구조로 정렬해주면 됩니다.

주로 효율이 좋은 bottom-up - O(n) 방식을 사용합니다.

top-down / O(n log n)과 비교해보면 효율 차이가 있는 모습입니다.

 

하지만 저는 효율이 구린 top-down 방식을 사용 했습니다.

 

왜 구린걸씀?

구린걸 먼저 써봐야 두방식의 차이를 확실하게 알 수 있을 것 같았음.

 

    public static void insert(ArrayList<Integer> heap, int data) {
        // 리스트의 맨 뒤에 데이터를 추가합니다.
        heap.add(data); 
        
        // targetIndex는 인자로 받은 data의 현재 인덱스를 의미합니다.
        int targetIndex = heap.size() - 1; 
        
        // parentNodeIndex는 위에서 설명한 공식대로 부모 노드의 인덱스를 의미합니다 (targetIndex / 2)
        int parentNodeIndex = targetIndex / 2; 


        while (targetIndex > 1 && heap.get(parentNodeIndex) < heap.get(targetIndex)) {
        // 부모 노드의 값이 현재 값 보다 작다면 두 값의 위치를 바꿔줍니다.
        // 부모노드의 값을 임시 변수에 저장하고, 부모노드 = 자식노드, 자식노드 = 부모노드 형태로 바꿔줍니다.
            int temp = heap.get(parentNodeIndex);
            heap.set(parentNodeIndex, heap.get(targetIndex));
            heap.set(targetIndex, temp);

            // 타겟 인덱스와 부모 인덱스를 업데이트
            targetIndex = parentNodeIndex;
            parentNodeIndex = targetIndex / 2;
        }
    }

 

 

데이터를 하나 넣을 때 마다 정렬 해주고 있습니다. 최대힙에서는 자식노드가 부모 노드보다 반드시 작다는 조건이 있기 때문에 항상 이 규칙을 지켜야 합니다. 

 

데이터 삽입시 데이터의 갯수 n만큼 연산이 이루어 집니다.

 

무슨말임?

리스트에 데이터 10개 삽입시 10번 연산해야함
리스트에 데이터 100개 삽입시 100번 연산해야함
for문 10회, 100회 돌려야함

넣어야할 데이터가 늘어나면 그에 비례해서 연산도 늘어남 = O(n)

 

 

이때 삽입 후 정렬 과정이 필요하니 정렬을 해야 할 텐데 이때 최악의 경우 트리의 마지막 부분까지 확인해야 할 수 있습니다. 트리는 log n 이라는 높이를 가지기 때문에 마지막 까지 확인 한다면 log n의 시간 복잡도를 가집니다. 따라서 각 데이터에 대해 log n 만큼의 연산이 필요할 수 있기 때문에 시간 복잡도는 O(n log n) 이 됩니다.

 

트리의 높이는 왜 log n임?

{1,2,3,4} 데이터를 완전이진트리로 나타내면
    4
  3  2
1

이런 형태인데 이는 높이가 2입니다.
따라서 log_2 4 = 2 
O(log n)

각 연산 O(n) 마다 O(log n)의 시간 복잡도를 가질 수 있기 때문에 O(n log n) 이라 표현

 

삭제

삭제는 트리의 root 값을 삭제하고 리스트의 마지막 값을 root로 변경합니다.
이후 위에서부터 아래로 내려가며 대소 비교하여 정렬합니다. 
최악의 경우 트리의 마지막 까지 확인해야 할 수 있기 때문에 시간 복잡도는 O(log n)이 됩니다.

마치며

구글링 해보니 관련 글에서 모두 root만 삭제하는 경우에 대해서만 설명 하고 있었습니다.

트리 중간 어딘가에 있는 값을 삭제 하면 안되는건가? 하는 생각이 들었고 동시에 힙이라는 자료구조를 왜 사용하는지에 대해 생각 해보았습니다.

 

힙 이라는 자료 구조는 최소값 혹은 최대값을 빠르게 찾기 위한 자료구조이기 때문에 굳이 root가 아닌 어딘가의 데이터를 찾아내서 지우려고 할 필요가 있을까 하는 생각이 들었습니다. 이런 경우 다른 자료구조를 고려 해보는 것도 좋지 않을까 하는 생각도 들었습니다.

 

따라서 필요하다면 만들어야 겠지만, 일반적인 약속으로는 root를 삭제하는게 맞다라는게 결론 입니다.