알고리즘/정렬

[알고리즘] 힙 정렬(Heap Sort)

chanmyung 2018. 5. 2. 10:30

힙 정렬(HeapSort)

힙이란?

http://devheat.tistory.com/12 참고

설명

힙의 최상위 노드에는 가장 큰 값이 존재한다는 특성을 이용해 정렬하는 알고리즘
최대 힙 혹은 최소 힙의 노드 삭제를 연속으로 수행해 값이 가장 큰 노드부터 내림차순 혹은 오름차순으로 꺼낼 수 있다.

구현

구현은 이전 포스팅 http://devheat.tistory.com/12 에서 만든 delete 메소드를 연달아 호출하면 된다.
최상위 노드를 꺼내고, 최하위 노드를 최상위에 위치시켜 다시 하향 heapify를 수행하는 것이 핵심

소스코드

import java.util.ArrayList;
class Heap {
private ArrayList<Integer> arr;
public Heap() {
arr = new ArrayList<>();
}
public Heap(int... values) {
this();
for (int v : values) {
insert(v);
}
}
private void heapUp(int index) {
int parentIdx = (index - 1) / 2;
if (arr.get(index) > arr.get(parentIdx)) {
int temp = arr.get(index);
arr.set(index, arr.get(parentIdx));
arr.set(parentIdx, temp);
heapUp(parentIdx);
}
}
private void heapDown(int index) {
int leftChildIndex = index * 2 + 1;
int rightChildIndex = index * 2 + 2;
int largerValueIndex = index;
if (leftChildIndex < arr.size() && arr.get(leftChildIndex) > arr.get(largerValueIndex)) {
largerValueIndex = leftChildIndex;
}
if (rightChildIndex < arr.size() && arr.get(rightChildIndex) > arr.get(largerValueIndex)) {
largerValueIndex = rightChildIndex;
}
if (largerValueIndex != index) {
int temp = arr.get(largerValueIndex);
arr.set(largerValueIndex, arr.get(index));
arr.set(index, temp);
heapDown(largerValueIndex);
}
}
public int size() {
return arr.size();
}
public void insert(int... values) {
for (int v : values) {
arr.add(v);
heapUp(arr.size() - 1);
}
}
public int delete() {
if (arr.size() == 0) throw new ArrayIndexOutOfBoundsException();
int removed = arr.remove(0);
if (arr.size() != 0)
arr.add(0, arr.remove(arr.size() - 1));
heapDown(0);
return removed;
}
public void printArray() {
arr.forEach(System.out::println);
}
public ArrayList<Integer> sorted() {
ArrayList<Integer> sorted = new ArrayList<>();
int size = arr.size();
for (int i = 0; i < size; i++) {
sorted.add(delete());
}
return sorted;
}
}
view raw Heap.java hosted with ❤ by GitHub

번외

이전 포스트와 마찬가지로 Generic Heap에도 정렬 기능을 추가할 수 있다.

import java.util.ArrayList;
import java.util.List;
public class GenericHeap<T extends Comparable<T>> {
private ArrayList<T> arr;
public GenericHeap() {
arr = new ArrayList<>();
}
public GenericHeap(T... values) {
this();
for (T v : values) {
insert(v);
}
}
private void heapUp(int index) {
int parentIdx = (index - 1) / 2;
if (arr.get(index).compareTo(arr.get(parentIdx)) >= 1) {
T temp = arr.get(index);
arr.set(index, arr.get(parentIdx));
arr.set(parentIdx, temp);
heapUp(parentIdx);
}
}
private void heapDown(int index) {
int leftChildIndex = index * 2 + 1;
int rightChildIndex = index * 2 + 2;
int largerValueIndex = index;
if (leftChildIndex < arr.size() && arr.get(leftChildIndex).compareTo(arr.get(largerValueIndex)) >= 1) {
largerValueIndex = leftChildIndex;
}
if (rightChildIndex < arr.size() && arr.get(rightChildIndex).compareTo(arr.get(largerValueIndex)) >= 1) {
largerValueIndex = rightChildIndex;
}
if (largerValueIndex != index) {
T temp = arr.get(largerValueIndex);
arr.set(largerValueIndex, arr.get(index));
arr.set(index, temp);
heapDown(largerValueIndex);
}
}
public int size() {
return arr.size();
}
public void insert(T... values) {
for (T v : values) {
arr.add(v);
heapUp(arr.size() - 1);
}
}
public T delete() {
if (arr.size() == 0) throw new ArrayIndexOutOfBoundsException();
T removed = arr.remove(0);
if (arr.size() != 0)
arr.add(0, arr.remove(arr.size() - 1));
heapDown(0);
return removed;
}
public void printArray() {
arr.forEach(System.out::println);
}
public List<T> sorted() {
List<T> sortedList = new ArrayList<>();
int arrSize = arr.size();
for (int i = 0; i < arrSize; i++) {
sortedList.add(delete());
}
return sortedList;
}
}

구현 힙 사용 예제 (Comparable을 구현한 String 클래스를 사용)

public class HeapSort {
public static void main(String[] args) {
System.out.println("======Integer heap=======");
Heap heap = new Heap(6, 1, 2);
heap.insert(5, 4, 7, 9);
System.out.println("after insert");
heap.printArray();
System.out.println("after sort");
heap.sorted().forEach(System.out::println);
System.out.println("======string heap=======");
GenericHeap<String> stringHeap = new GenericHeap<>("a", "c", "e", "b");
stringHeap.insert("d", "g", "f");
System.out.println("after insert");
stringHeap.printArray();
System.out.println("after sort");
stringHeap.sorted().forEach(System.out::println);
}
}
view raw HeapSort.java hosted with ❤ by GitHub