📌Today I Learned

힙(Heap)

완전이진트리의 일종.
부모 노드와 자식 노드 간에 특정한 조건을 만족하는 자료구조.

완전 이진 트리

부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있고, 마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있는 트리 구조.

레벨

루트 노드부터 시작하여 트리의 몇 번째 층에 있는지 나타낸다.
루트 노드의 레벨 = 0

높이

리프 노드부터 시작하며, 루트 노드의 높이는 트리의 전체 높이가 된다.

힙의 종류

최대 힙(Max Heap), 최소 힙(Min Heap)

최대 힙(Max Heap)

모든 부모 노드가 그 자식 노드보다 크거나 같은 값을 가진다.
루트 노드는 전체 힙 중에서 가장 큰 값을 가진다.

최소 힙(Min Heap)

모든 부모 노드가 그 자식 노드보다 작거나 같은 값을 가진다.
루트 노드는 전체 힙 중에서 가장 작은 값을 가진다.

힙 구현 방법

배열(Array)

루트 노드가 배열의 첫 번째 인덱스에 위치한다.

인덱스가 1부터 시작하는 경우,
i 인덱스에 있는 노드의 왼쪽 자식 노드: 2 * i 인덱스에 위치
i 인덱스에 있는 노드의 오른쪽 자식 노드: 2 * i + 1 인덱스에 위치

힙 구현 코드 예시

package datastructure;

public class MinHeap {
	public int[] heap;
	public int size;

	// 힙 구축 (min heap)
	public void buildMinHeap(int[] arr) {
		this.size = arr.length;
		this.heap = new int[size + 1]; // heap[0]은 미사용
		System.arraycopy(arr, 0, heap, 1, size); // heap[1]이 root

		// 부모 노드들을 역으로 순회
		// 힙의 가장 마지막에 위치한 부모 노드의 인덱스 = 전체 힙 사이즈 / 2
		for (int i = size / 2; i >= 1; i--) {
			minHeapify(i);
		}
	}
	
	// heapify()
	// 최소 힙에서 부모 노드가 자식 노드보다 큰 경우 위치를 바꾼다.
	// 재귀적으로 진행하여 전체 힙이 최소 힙의 조건을 만족하도록 한다.
	// 최소 힙의 조건: 모든 부모 노드는 자식 노드보다 작거나 같아야 한다.
	
	// 힙 구조로 재배열
	public void minHeapify(int i) {
		int left = 2 * i;
		int right = 2 * i + 1;
		int smallest;
		
		//왼쪽 자식 노드와 비교
		if (left <= size && heap[left] < heap[i]) {
			smallest = left;
		} else {
			smallest = i;
		}
		
		//위에서 비교한 값과 오른쪽 자식 노드와 비교
		if (right <= size && heap[right] < heap[smallest]) {
			smallest = right;
		}
		
		// 자식 노드가 더 작으면 위치를 바꾸고, minHeapify 재귀 호출
		if (smallest != i) {
			swap(i, smallest);
			minHeapify(smallest);	// 재귀 호출
		}
	}
	
	// 두 요소의 위치를 바꿈
	public void swap(int i, int j) {
		int temp = heap[i];
		heap[i] = heap[j];
		heap[j] = temp;
	}
	
	// 힙 배열 출력
	public void printHeapArray() {
		for (int i = 1; i <= size; i++) {
			System.out.println(heap[i] + " ");
		}
		System.out.println();
	}
}

힙 구현코드 호출하기

package datastructure;

public class Clientmain {

	public static void main(String[] args) {

		int[] heapArray = {0, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
		MinHeap minHeap = new MinHeap();
		minHeap.buildMinHeap(heapArray);
		minHeap.printHeapArray();
	}

}

힙 시간 복잡도

O(log n)
heapify()가 힙의 높이만큼 재귀호출을 한다.

buildHeap() - O(n)

힙의 삽입/삭제 연산 - O(log n)
-> 트리의 재정렬 진행

최대값/최소값 구하는경우 - O(1)
-> 힙의 루트 값 조회

힙 정렬(Heap Sort)

힙을 이용하여 배열을 정렬하는 알고리즘.
정렬되지 않은 배열을 최대 힙이나 최소 입으로 구성하고, 루트 노드를 가장 마지막 노드와 교환한 후 힙 크기를 줄이는 방식.

각 원소가 k 위치만큼 떨어져 있는 배열인 k-sort 배열을 정렬할 때 가장 효율적인 방법이다.

장점

최악, 최선의 경우에도 평균 O(n log n)의 시간 복잡도 보임.
별도의 메모리를 사용하지 않는 제자리 정렬(in-place sorting) 방식 사용.
-> 일정한 성능을 보임과 동시에 별도의 메모리를 사용하지 않는다.

단점

숫자가 같은 경우에도 스왑이 발생하여 안정적이지 않은 정렬 방법이다.

구현 예시

package datastructure;

public class HeapSort {

	public void heapSort(int[] inputArray) {

		MinHeap minHeap = new MinHeap();

		// 힙 생성
		minHeap.buildMinHeap(inputArray);

		// 힙 정렬
		int j = 0;
		for (int i = minHeap.size; i >= 2; i++) {
			inputArray[j] = minHeap.heap[1]; // 힙의 root(최소값)을 배열에 저장
			j++;
			minHeap.swap(1, i); // 힙의 root와 마지막 요소를 바꿈
			minHeap.size--; // 힙의 크기를 줄임
			minHeap.minHeapify(1); // 힙을 재배열
		}

		// 힙의 마지막 root값을 배열 마지막에 저장
		inputArray[j] = minHeap.heap[1];
	}
}

시간 복잡도

O(n log n)

힙 생성 - O(n)

힙 정렬에서 힙에서 가장 큰(또는 작은) 원소를 제거하고 힙 재정렬하는 과정을 n번 반복.
제거 연산 - O(log n)

-> O(n log n)

=> O(n) + O(n log n) = O(n log n)

출처
https://yozm.wishket.com/magazine/detail/2312/