[자료구조] 힙(Heap)

힙(Heap)

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조
위키피디아 - 힙(자료구조)

완전이진트리?

마지막 두 레벨을 제외한 모든 노드의 차수가 2이며, 마지막 레벨의 노드가 왼쪽에 몰려있는 이진 트리

힙의 특징

최소 힙과 최대 힙

힙은 최소 힙과 최대 힙으로 나뉜다.

비교	최소 힙	최대 힙
조건	자식 노드의 값이 부모보다 커야한다.	부모의 값이 자식 노드의 값보다 커야한다.

힙의 원리

힙은 리스트(배열)로 표현될 수 있으며 각 노드의 인덱스가 index라면 왼 쪽 자식 노드의 인덱스는 index * 2 + 1, 오른 쪽 자식 노드의 인덱스는 index * 2 + 2이다.

힙은 새로운 노드를 추가할 때 힙의 마지막 위치(리스트의 끝)에 추가한 후 상향 heapify 한다.
또한 최상위 노드를 삭제할 때엔(사실 pop이라는 표현이 더 맞겠다.) 최상위 노드를 빼낸 후 마지막 노드(리스트의 마지막 인덱스의 노드)의 위치를 최상위로 옮긴 후 하향 heapify한다. 이과정에서 남은 노드중 값이 가장 큰 노드가 최상위로 올라오고, 노드는 원래 위치를 찾아간다.

상향 heapify

부모 노드와 값을 비교해 자신이 더 크다면 부모 노드와 자리를 바꾸는 작업
재귀적으로 수행되며 힙에서 가장 큰 값 N이 추가된 후 이루어지는 상향 heapify는 N의 레벨이 1씩 줄어들어 이내 1레벨에 도달하는 모습을 보여준다.

하향 heapify

왼 쪽 자식 노드와 오른 쪽 자식 노드, 그리고 자기 스스로의 값을 비교해 값이 가장 큰 노드와 자리를 바꾼다. (스스로가 가장 큰 경우 수행을 멈춘다.) 역시 재귀적으로 수행된다.

힙 구현

정수 힙 구현

	import java.util.ArrayList;
	public 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);
	}

view raw Heap.java hosted with ❤ by GitHub

번외

제네릭을 이용해 Comparable 인터페이스를 구현한 구현체들을 담는 Heap을 구현할 수 있다.

소스코드

	import java.util.ArrayList;
	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);
	}
	}

view raw GenericHeap.java hosted with ❤ by GitHub

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

	public class HeapExample {
	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 delete");
	heap.delete();
	heap.printArray();
	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 delete");
	stringHeap.delete();
	stringHeap.printArray();
	}
	}

view raw HeapExample.java hosted with ❤ by GitHub