힙(heap) 이란 ?

 

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

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

그림같은 자료를 가져다 쓴 곳입니다! ( 또한 잘 정리가 되어 있어서 참고 하면서 공부 했습니다. )

"C언어로 쉽게 풀어쓴 자료구조" 를 가지고 공부 중에 있습니다. 책의 내용을 정리해서 쓰고 있습니다.

여기는 그냥 제가 공부한 것을 정리하는 TIL 공간입니다. ( 책과 블로그 글 내용이 비슷하네요 ) 

 

우선순위 큐에 대해서는 다른 글에서 따로 정리하려 한다. 

힙(heap)의 개념

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 힙은 느슨한 정렬 상태를 유지한다. (완전히 정렬된 것은 아니지만, 전혀 정렬이 안된 것도 아님)
• 힙 트리에서는 중복된 값을 허용한다.
• 히프의 목적은 삭제 연산이 수행될 때마다 가장 큰 값을 찾아내기만 하면 되는 것이다(가장 큰 값은 루트 노드)

 

 

힙(heap)의 종류

• 최대 힙(max heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • key(부모 노드) >= key(자식 노드)

 

• 최소 힙(min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  • key(부모 노드) <= key(자식 노드)

 

 

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

 

 

힙(heap)의 구현 

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 프로그램 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0는 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가 되어도 변하지 않는다. 

 

 

힙에서의 부모 노드와 자식 노드의 관계 

• 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
• 오른쪽 자식의 인덱스 = (부모의 인덱스) *2 + 1
• 부모의 인덱스 = (자식의 인덱스) / 2

 

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

 

이렇게 각각의 노드들은 1번 인덱스부터 번호가 지정되어 있다. 이진트리 이므로 루트노드의 왼쪽자식은 2번, 오른쪽 자신은 3번 이런식으로 번호를 정하다 보면 위의 공식이 나오게 된다. 

 

힙(heap) 삽입 연산

• 히프에 새로운 요소가 들어오면, 일단 새로운 노드를 히프의 마지막 노드로 삽입된다.
• 따라서 삽입 후에 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시켜 주어야 한다.

 

 

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

 

 

이렇게 이론적으로 그림을 통해서 삽입연산을 보면 이해는 잘 된다. 하지만 구현은 정말 쉽지 않았던 것 같다..  그리고 이진탐색트리에서도 그랬지만, 삽입 연산보다는 삭제연산이 더 어렵다  

코드를 읽는거랑 구현하는 건 천지 차이일텐데..  ( 읽는 것도 어렵다. )  

 

이제 자바를 이용해서 최대 힙의 삽입연산을 구현해보자.

public class MaxHeapTest {
    private ArrayList<Integer> heap;
 
    public MaxHeapTest() {
        heap = new ArrayList<>();
        heap.add(0);  // 인덱스 0번은 버림
    }
 
    public void insert(int val) {
        heap.add(val);
        int p = heap.size()-1;
 
        while (p > 1 && heap.get(p / 2) < heap.get(p)) {
            int temp = heap.get(p / 2);
            heap.set(p/2, heap.get(p));
            heap.set(p, temp);
 
            p = p / 2;
        }
    }

 

 

 

힙(heap 삭제연산

• 최대 힙에서 삭제 연산은 최대값을 가진 요소를 삭제하는 것이다. 
• 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. 

 

 

 

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

 

 

 

 

이번에는 최대힙의 삭제 연산을 구현해보자.

 public int delete() {
        if (heap.size()-1 < 1) {
            return 0;
        }
 
        int deleteItem = heap.get(1);
        heap.set(1,heap.get(heap.size()-1));
        heap.remove(heap.size()-1);
 
        int parent = 1;
        int child = 2;
        while (child < heap.size()) {
            int max = heap.get(child);
 
            if (child < heap.size()-1 && max < heap.get(child + 1)) {
                max = heap.get(child + 1);
                child++;
            }
 
            if (heap.get(parent) > max) {
                break;
            }
 
            int temp = heap.get(parent);
            heap.set(parent, heap.get(child));
            heap.set(child, temp);
            parent = child;
            child+=2;
 
        }
        return deleteItem;
 
    }