[자료구조] 힙과 힙소트

힙

힙은 자료구조의 하나로 최대값, 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로한다.

l  최대힙 : 부모노드의 값이 자식노드보다 크다.

l  최소힙 : 자식노드의 값이 부모노드보다 크다.

부모와 자식 노드간의 대소관계만 정해지고, 자식 노드간의 대소관계는 정해지지 않는다.

 

힙정렬

힙을 구성하여 정렬을 수행하는 것을 힙정렬이라 한다.

최대힙을 이용하여 정렬을 수행하는 방법은 다음과 같다.

1. 최대힙을 구성한다.

2. 최대힙의 루트값을 배열의 맨뒤로 보내고 배열의 사이즈를 하나 줄인다.

3. 변경된 배열에 대해서 최대힙을 다시 구성한다.

4. 2 ~ 3의 과정을 배열의 길이가 1이 될때까지 반복한다.

 

소스코드[Java]

public class MaxHeapSort {

    public static void main(String[] args) {
        
        // 데이터 입력
        MaxHeap heap = new MaxHeap(10);
        heap.insert(5);
        heap.print();
        heap.insert(6);
        heap.print();
        heap.insert(2);
        heap.print();
        heap.insert(3);
        heap.print();
        heap.insert(9);
        heap.print();
        heap.insert(40);
        heap.print();
        heap.insert(33);
        heap.print();
        heap.insert(11);
        heap.print();
        heap.insert(15);
        heap.print();
        heap.insert(100);
        heap.print();
        
        // 데이터 삭제
//      System.out.println("remove : " + heap.remove());
//      heap.print();
//      System.out.println("remove : " + heap.remove());
//      heap.print();
//      System.out.println("remove : " + heap.remove());
//      heap.print();
//      System.out.println("remove : " + heap.remove());
//      heap.print();
//      System.out.println("remove : " + heap.remove());
//      heap.print();
//      System.out.println("remove : " + heap.remove());
//      heap.print();
//      System.out.println("remove : " + heap.remove());
//      heap.print();
//      System.out.println("remove : " + heap.remove());
//      heap.print();
//      System.out.println("remove : " + heap.remove());
//      heap.print();
//      System.out.println("remove : " + heap.remove());
//      heap.print();
//      System.out.println("remove : " + heap.remove());
//      heap.print();
        
        // 정렬후 출력
        int[] array = heap.sort();
        for (int i : array) {
            System.out.print(i);
            System.out.print(" ");
        }
    }
}

class MaxHeap {

    int capacity;
    int[] array;
    int currentLocation;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        array = new int[capacity];
    }

    public void insert(int value) {

        if (currentLocation == capacity) {
            System.out.println("heap is full");
            return;
        }

        array[currentLocation] = value;
        int parentLocation = (currentLocation - 1) / 2;

        // 데이터 추가후 힙을 재구성한다. 
        insert_sort(parentLocation, currentLocation++);
    }

    /**
     * 데이터 추가후 힙 재구성
     * 현재 노드의 값이 부모노드의 값보다 크면 변경후 재확인
     * 
     * @param parentLocation
     * @param currentLocation
     */
    private void insert_sort(int parentLocation, int currentLocation) {

        if (parentLocation >= 0 && array[parentLocation] < array[currentLocation]) {
            int temp = array[parentLocation];
            array[parentLocation] = array[currentLocation];
            array[currentLocation] = temp;

            currentLocation = parentLocation;
            parentLocation = (currentLocation - 1) / 2;
            insert_sort(parentLocation, currentLocation);
        }
    }
    
    public int remove() {

        if (currentLocation == 0){
            System.out.println("heap is empty");
            return -1;
        }
        
        // 데이터 삭제 후 배열의 마지막 위치의 값을 첫번째(루트노드) 위치로 이동한다. 
        int remove = array[0];
        array[0] = array[--currentLocation];
        array[currentLocation] = 0;

        // 자식 노드중 보다 큰 값과 정렬을 진행한다. 
        if(array[1] >= array[2]){
            remove_sort(1, 0);
        } else {
            remove_sort(2, 0);
        }
        
        return remove;
    }

    /**
     * 현재값과 자식노드의 값을 비교하여 정렬
     * 
     * @param childLocation
     * @param currentLocation
     */
    private void remove_sort(int childLocation, int currentLocation) {

        if (childLocation < capacity && array[childLocation] > array[currentLocation]) {
            int temp = array[childLocation];
            array[childLocation] = array[currentLocation];
            array[currentLocation] = temp;

            currentLocation = childLocation;
            int leftChild = (currentLocation * 2) + 1;
            int rightChild = (currentLocation * 2) + 2;
            
            // 자식 노드중 보다 큰 값과 정렬을 진행한다. 
            if((leftChild < capacity && rightChild < capacity && array[leftChild] >= array[rightChild]) || (leftChild < capacity && rightChild >= capacity)){
                remove_sort(leftChild, currentLocation);
            } else if ((leftChild < capacity && rightChild < capacity && array[leftChild] < array[rightChild])) {
                remove_sort(rightChild, currentLocation);
            }
        }
    }
    
    
    /**
     * 힙의 데이터를 소팅해서 반환
     * 
     * @return
     */
    public int[] sort() {
        int index = 0;
        int[] array = new int[currentLocation];
        
        while(true) {
            int value = remove();
            
            if(value == -1)
                break;
            
            array[index++] = value;
        } 
        
        return array;
    }

    public void print() {
        for (int i : array) {
            System.out.print(i);
            System.out.print(" ");
        }
        System.out.println("");
    }
}

 

 

참고

http://exynoa.tistory.com/249

http://www.slideshare.net/JoHeeyeon/ss-22500348?qid=079c9306-f027-4ea8-b8e7-1271644bfeee&v=default&b=&from_search=1