Heap and Heap sort

오후 2:38:00

이번 Posting에서는 heap과 heap을 이용한 sorting에 대하여 정리를 할 것이다.

Heap

힙은 트리의 일종으로 최대힙과 최소힙이 있다. 정의는 다음과 같다.

"완전 트리이면서 root가 모든 경우에 자식들보다 커야한다."

완전 트리는 node가 순서에 맞게 들어있는 트리이고 다음과 같은 모양을 갖고 있다.

위와 같이 노드들이 순서대로 들어가는데 root가 자식보다 커야한다는 가정을 하면 최대 힙이 되는 것이고, root가 자식 보다 작아야한다는 가정을 한다면 최소힙이 되는 것이다.

root가 자식보다 크거나 작다는 규칙은 모든 서브트리들에 적용이된다.

만약 힙에서 제거를 하게된다면 가장 위의 root 값이 제거된다.

Heap Sorting

위와 같은 힙의 성질을 이용해 정렬을 할 수 있다. 랜던한 숫자들을 힙으로 만들어 놓고, 힙에서 하나씩 제거하면서 정렬을 할 수 있다.

구현은 다음과 같다.

/**
 * Created by im501 on 2017-08-18.
 */
public class MyHeap {
    private int[] data;
    private int size;
    private int maximumSize;

    public MyHeap() {
        data = new int[100];size = 0;
    }

    public MyHeap (int maximumSize) {
        this.maximumSize = (maximumSize < 1) ? 100 : maximumSize;
        data = new int[this.maximumSize];size = 0;
    }

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

    public boolean isFull() {
        return (this.size == this.maximumSize);
    }

    public void clear() {
        data = null;
    }

    public void insert(int num) {
        int pointer;
        if (isFull()) {
            throw new ArrayIndexOutOfBoundsException();
        }else {
            data[size] = num;
            pointer = size++;

            while (pointer > 0 && data[pointer] > data[(pointer - 1) / 2]) {
                int tmp = data[pointer];
                data[pointer] = data[(pointer - 1) / 2];
                data[(pointer - 1) / 2] = tmp;
                pointer = (pointer - 1) / 2;
            }
        }
    }

    public int delete() {
        int t;
        if (isEmpty()) {
            throw new ArrayIndexOutOfBoundsException();
        }else {
            t = data[0];
            data[0] = data[--size];
            data[size] = 0;
            reHeap();
            return t;
        }
    }

    public void reHeap() {
        int pointer = 0;
        while (pointer * 2 + 1 < size) {
            if (data[pointer * 2 + 1] > data[pointer * 2 + 2]) {
                int t = data[pointer];
                data[pointer] = data[pointer * 2 + 1];
                data[pointer * 2 + 1] = t;
                pointer = pointer * 2 + 1;
            }else {
                int t = data[pointer];
                data[pointer] = data[pointer * 2 + 2];
                data[pointer * 2 + 2] = t;
                pointer = pointer * 2 + 2;
            }
        }
    }


    public int[] sort() {
        int[] sort = new int[this.size];
        for (int i = 0; i < sort.length; i++) {
            sort[i] = this.delete();
        }
        return sort;
    }


    public static void main(String[] args) {
        MyHeap heap = new MyHeap(100);
        heap.insert(5);
        heap.insert(3);
        heap.insert(7);
        heap.insert(4);
        heap.insert(2);
        heap.insert(6);
        heap.insert(1);
        int[] arr = heap.sort();
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

    }

}

이 블로그 검색

Do.

Heap and Heap sort

이 블로그의 인기 게시물

웹툰 무료로 볼 수 있는 사이트

BackJoon 1011, Fly me to the alpha centauri, 규칙 찾기 문제

BaekJoon 6591, 이항 쇼다운 조합문제