[Sort] 힙 정렬(Heap Sort]

힙 정렬(Heap Sort)

 

정의: 힙이라는 자료구조를 이용하여 정렬하는 방법

힙은 삭제 연산을 수행하면 가장 최상위 루트원소를 반환한다.

최상위 루트원소는 힙 내부에서 가장 큰 원소이다.

힙정렬....

힙을 이용해서 정렬을 하므로 굉장히 쉽게 사용되죠~

왜냐면 힙 구현해 놓고 삭제 연산을 하면 정렬이 되니깐요!!!

한번 봅시다 !

---

1단계

 

자 이렇게 최대 힙이 구성이 되어있습니다!!!

여기서 힙의 삭제연산을 합니다!!

삭제 연산은 루트 를 반환한다고 했죠???

루트를 반환하고 힙은 다시 최대 힙을 구성합니다!

아래처럼 말이죠~

 

1단계 끝!!

---

---

2단계

삭제 연산을 진행해야 겠죠???

아래처럼 진행됩니다!!

 

계속 힙안에 있는 원소를 삭제 시키는 겁니다...

---

---

3단계

계속 삭제...

힙이 보잘것 없어서 아예 없어 질때까지...

 

---

---

4단계

 

---

---

5단계

 

---

---

6단계

 

---

---

7단계

---

---

8단계

자 이렇게 마무리가 됩니다!!

---

 

 

이 힙 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!

모든 케이스에 대해

 

를 갖습니다!!!

자 그럼 소스 코드로 예제를 살펴 봅시다~

HeapMain.java

 

package Heap;
 
public class HeapMain {
    public static void main(String[] args) {
        int[] arr = { 69, 10, 30, 2, 16, 8, 31, 22 };
        HeapSort.heapSort(arr);
    }
}
 

HeapSort.java

 

 
package Heap;
 
import Selection.SelectionSort;
 
public class HeapSort {
    public static void heapSort(int[] arr) {
        Heap heap = new Heap();
 
        for (int i = 0; i < arr.length; i++) {
            heap.insertHeap(arr[i]);
        }
 
        for (int i = arr.length - 1; i >= 0; --i) {
            arr[i] = heap.deleteHeap();
 
        }
        System.out.println("힙 정렬 :");
        SelectionSort.printArr(arr);
    }
}
 

Heap.java

 

 
package Heap;
 
public class Heap {
    private int heapSize;
    private int itemHeap[];
 
    public Heap() {
        heapSize = 0;
        itemHeap = new int[50];
    }
 
    public void insertHeap(int item) {
        int i = ++heapSize;
 
        while ((i != 1) && (item > itemHeap[i / 2])) {
            itemHeap[i] = itemHeap[i / 2];
            i /= 2;
        }
 
        itemHeap[i] = item;
    }
 
    public int getHeapSize() {
        return this.heapSize;
    }
 
    public int deleteHeap() {
        int parent, child;
        int item, tmp;
        item = itemHeap[1];
        tmp = itemHeap[heapSize--];
        parent = 1;
        child = 2;
 
        while (child <= heapSize) {
            if ((child < heapSize) && (itemHeap[child] < itemHeap[child + 1]))
                child++;
 
            if (tmp >= itemHeap[child])
                break;
 
            itemHeap[parent] = itemHeap[child];
            parent = child;
            child *= 2;
        }
 
        itemHeap[parent] = tmp;
        return item;
    }
}
 

실행 결과는 아래와 같습니다!!!