힙(heap)

힙 이란?

완전 이진트리의 일종이며, 우선순위 큐를 위해 만들어진 자료구조이다.

 

우선순위 큐?

• 우선순위 개념을 큐에 적용한 자료 구조이다.
• 가장 우선순위가 높은 데이터가 먼저 나간다.
• 배열, 연결 리스트, 힙으로 구현 가능하다. 이중 힙으로 구현하는 것이 가장 성능이 좋다.

 

힙 특징

• 힙은 일종의 반정렬 상태를 유지한다.( 큰 값이 위에 있으면 작은 값은 아래에 있다는 정도 )
• 부모 노드의 값이 자식 노드보다 항상 크거나 작은 이진트리이다.
• 중복을 허용한다.
• 최대값, 최소값을 조회하기 좋다

 

힙 종류

• 최대 힙
  • 부모 노드가 자식 노드보다 크거나 같은 완전 이진트리
• 최소 힙
  • 부모 노드가 자식 노드보다 작거나 같은 완전 이진트리

 

힙 구현

• 힙을 저장하는 표준 자료구조는 배열이다.
• 배열의 첫 번째 인덱스인 0은 사용하지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
• 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  부모의 인덱스 = (자식의 인덱스) / 2

힙의 삽입

1. 힙에 새로운 요소가 들어오면, 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 비교하여 교환( 힙의 정의에 따라 )

힙의 삭제

1. 루트 노드를 삭제한다. (최대 힙이면 루트 노드가 최대 값)
2. 삭제한 노드에는 힙의 마지막 노드 가져온다.
3. 재정렬( 자식 노드와 값을 비교 및 교환 )

구현

public class Heap {

    // TODO comparator 를 생성자로 받아서 int 배열이 아닌 다양한 객체 배열로 사용 가능하도록 수정하자.

    private static final int DEFAULT_CAPACITY = 10; // 기본 배열 사이즈

    private boolean isMaxHeap;  // 최대 힙 여부 ( TRUE = 최대 힙, FALSE = 최소 힙 )
    private int size;           // 실제 요소 개수
    private int[] array;        // 요소를 담을 배열

    public Heap() {
        this.array = new int[DEFAULT_CAPACITY];
        this.size = 0;
        this.isMaxHeap = false;
    }

    public Heap( int capacity ) {
        this(capacity, false);
    }

    public Heap( int capacity, Boolean isMaxHeap ) {
        this.array = new int[capacity];
        this.size = 0;
        this.isMaxHeap = isMaxHeap;
    }

    private int getParentIndex( int index ){
        return index / 2;
    }

    private int getLeftChildIndex( int index ){
        return index * 2;
    }

    private int getRightChildIndex( int index ){
        return index * 2 + 1;
    }

    /**
     * 배열 사이즈 증축
     * @param newCapacity 세로운 용적 크기
     * */
    private void resize( int newCapacity ){
        // 새 배열 생성
        int[] newArray = new int[newCapacity];

        // 데이터 복사
        for ( int i = 1; i<= size; i++ ){
            newArray[i] = array[i];
        }
        this.array = newArray;
    }

    /**
     * 삽입
     */
    public void add( int val ){

        // 배열이 꽉찬 경우 배열 사이즈 증축
        int index = size + 1;
        if( index == array.length ) {
            resize(array.length * 2);
        }

        // 2. 새로운 노드를 부모 노드들과 비교하여 교환( 힙의 정의에 따라 )
        while( true ){
            int parentIndex = getParentIndex(index);
            int parentValue = array[parentIndex];

            // 최대 힙 이냐 에 따른 조건에 따라 반복문 종료
            if( isMaxHeap ){
                // 최대 힙
                if( parentValue >= val ){
                    break;
                }
            } else {
                // 최소 힙
                if( parentValue <= val ){
                    break;
                }
            }

            // 종료 안되었다면 부모와 교환 해야 한다.
            array[index] = parentValue;
            index = parentIndex;
        }

        // 마지막 삽입
        array[index] = val;
        size++;
    }

    /**
     * 추출
     */
    public int delete(){
        // 데이터 유무 확인
        if( size == 0 ){
            throw new NoSuchElementException();
        }

        // 루트 노드를 삭제한다. (최대 힙이면 루트 노드가 최대 값)
        // 삭제한 노드에는 힙의 마지막 노드 가져 온다.
        int result = array[1];      // 반환할 데이터
        int lastOne = array[size];  // 마지막 요소

        array[size] = 0;           // 마지막 요소를 비운다.
        size--;

        // 재정렬( 자식 노드와 값을 비교 및 교환 )
        int parentIndex = 1;
        int childIndex;
        while( ( childIndex = getLeftChildIndex( parentIndex ) ) <= size ) {
            int rightIndex = getRightChildIndex( parentIndex );
            int childValue = array[childIndex]; // 왼쪽 자식 값

            if( isMaxHeap ){
                if( rightIndex <= size && array[rightIndex] > childValue ){
                    // 더 큰 자식과 비교 해야한다.
                    childIndex = rightIndex;
                    childValue = array[childIndex];
                }

                if( lastOne >= childValue ){
                    break;
                }

            } else {
                if( rightIndex <= size && array[rightIndex] < childValue ){
                    // 더 작은 자식과 비교 해야한다.
                    childIndex = rightIndex;
                    childValue = array[childIndex];
                }

                if( lastOne <= childValue ){
                    break;
                }
            }

            array[parentIndex] = childValue;
            parentIndex = childIndex;
        }

        array[parentIndex] = lastOne;

        /*
         *  용적의 사이즈가 최소 용적보다는 크면서 요소의 개수가 전체 용적의 1/4일경우
         *  용적을 반으로 줄임(단, 최소용적보단 커야함)
         */
        if( array.length > DEFAULT_CAPACITY && size < array.length / 4 ) {
            resize( Math.max( DEFAULT_CAPACITY, array.length / 2 ) );
        }

        return result;
    }

    public int size() {
        return this.size;
    }

    public int peek() {
        if( array[1] == 0 ) {
            throw new NoSuchElementException();
        }

        return array[1];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int[] toArray() {
        return Arrays.copyOf(array, size + 1);
    }
}

---

참조

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

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

https://st-lab.tistory.com/205

자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기