알고리즘/정렬
[알고리즘] 힙 정렬(Heap Sort)
chanmyung
2018. 5. 2. 10:30
힙 정렬(HeapSort)
힙이란?
http://devheat.tistory.com/12 참고
설명
힙의 최상위 노드에는 가장 큰 값이 존재한다는 특성을 이용해 정렬하는 알고리즘
최대 힙 혹은 최소 힙의 노드 삭제를 연속으로 수행해 값이 가장 큰 노드부터 내림차순 혹은 오름차순으로 꺼낼 수 있다.
구현
구현은 이전 포스팅 http://devheat.tistory.com/12 에서 만든 delete 메소드를 연달아 호출하면 된다.
최상위 노드를 꺼내고, 최하위 노드를 최상위에 위치시켜 다시 하향 heapify를 수행하는 것이 핵심
소스코드
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
번외
이전 포스트와 마찬가지로 Generic Heap에도 정렬 기능을 추가할 수 있다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 클래스를 사용)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |