#015 힙 정렬

# 문제)

아래와 같이 정렬되지 않은 배열이 있을때 힙 정렬을 사용하여 오름차순 정렬하여라.

5

2

4

3

1

힙 정렬의 힙의 특징을 이용하여 정렬하는 방식을 말한다.

힙의 특징은 아래와 같다.

힙은 완전 이진트리 구조를 활용된다.

추가 시에는 맨 마지막 원소에 추가되며

루트 방향으로 올라가면서 부모와 값을 비교해 적절한 위치를 찾는다.

삭제 시에는 

최소 힙으로 구성했을 경우, 최소값을

최대 힙으로 구성했을 경우, 최대값을 반환하고 삭제된다.

또한 삭제 후 이진트리 구조를 유지하기 위해 원소의 마지막 값을 root에 위치하여

자식 중 우선순위가 높은 값과 비교하여 원소의 마지막 값의 위치를 찾는다.

즉, 힙 정렬의 경우, 추가시에 정렬이 된 상태로 들어가게 되며

삭제 시에는 최소(또는 최대) 값을 반환하기 때문에 이를 활용하여 정렬을 수행한다.

*힙 구현 시 배열을 이용해 구현할거임.

*0인덱스는 비워둔다. (힙 구현 편의성을 위해)

*따라서 root 인덱스는 1.

*왼쪽 자식 인덱스는 index*2, 오른쪽 자식 인덱스는 (index*2)+1

*부모 인덱스는 index/2

package dataStructure.heap;

public class BasicHeap {

   

    private int array[] = new int[10];

    private int size = 0;

   

    public int getLeftChild(int parent) {

        return parent*2;

    }

   

    public int getRightChild(int parent) {

        return getLeftChild(parent)+1;

    }

   

    public int getParent(int currentIndex) {

        return currentIndex/2;

    }

   

    public void add(int value) {

        array[++size] = value;

        int currentIndex = size;

        while(currentIndex != 1) {

           if(array[currentIndex] < array[getParent(currentIndex)]) {

               swap(getParent(currentIndex), currentIndex);

               currentIndex = getParent(currentIndex);

           }else {

               break;

           }

        }

    }

   

    private void swap(int swapIndex1, int swapIndex2) {

        int temp = array[swapIndex1];

        array[swapIndex1] = array[swapIndex2];

        array[swapIndex2] = temp;

    }

   

    public int remove() {

        int removedValue = array[1];

        int parentIndex = 1;

        array[parentIndex] = array[size--];

        while(parentIndex < size) {

            if(array[getHighPriorityChild(parentIndex)] < array[parentIndex]) {

                swap(getHighPriorityChild(parentIndex), parentIndex);

                parentIndex = getHighPriorityChild(parentIndex);

            }else {

                break;

            }

        }

        return removedValue;

    }

   

    public int getHighPriorityChild(int parent) {

        if(size == 0) {

            return 0;

        }else if(getLeftChild(parent) == size) {

            return getLeftChild(parent);

        }

       

        if(array[getLeftChild(parent)] > array[getRightChild(parent)]) {

            return getRightChild(parent);

        }

        return getLeftChild(parent);

    }

   

    public boolean isEmpty() {

        if( size == 0) {

            return true;

        }

        return false;

    }

   

    @Override

    public String toString() {

        // TODO Auto-generated method stub

        StringBuilder result = new StringBuilder();

        result.append("[");

       

        int i = 1;

        while( i<=size ) {

            result.append(array[i]);

            if(i != (size)) {

                result.append(",");

            }

            i++;

        }

        result.append("]");

        return result.toString();

    }

   

    public static void main(String[] args) {

        BasicHeap heap = new BasicHeap();

        heap.add(5);heap.add(2);heap.add(4);heap.add(3);heap.add(1);

        System.out.println(heap);

       

        while(!heap.isEmpty()) {

            System.out.println(heap.remove());

            System.out.println("result : "+heap);

        }

    }

}