자료구조&알고리즘_힙

힙 (Heap)

우선순위 큐는 일반적인 FIFO인 큐와 달리 우선순위가 높은 요소가 먼저 나가는 개념이다.
힙은 우선순위 큐를 구현하기 위한 가장 적합한 방법이다.

우선순위 큐 !== 힙

힙의 특징

• 우선순위가 높은 요소가 먼저 나간다.
• 루트가 가장 큰 값이 되는 최대 힙(Max Heap)와 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있다.

힙 요소 추가 알고리즘

1. 추가된 요소를 트리의 가장 마지막 정점에 위치시킨다.
2. 요소의 부모 정점과 비교하여 우선순위가 높다면 부모 정점과 순서를 바꾼다.
3. 1,2번을 반복하면 가장 우선순위가 높은 정점이 루트가 된다.
4. 시간복잡도는 O(Log N)이다.

힙 요소 제거 알고리즘

1. 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다. (요소 제거는 루트만 가능)
2. 루트 정점의 두 자식 정점 중 우선순위가 높은 정점과 바꾼다.
3. 두 자식의 정점이 우선순위가 더 낮을 때까지 반복
4. 시간복잡도는 O(Log N)이다.

힙 구현 방법

요소 추가

class MaxHeap {
	constructor() {
		this.heap = [null];
	}

	insert(value) {
		this.heap.push(value);
		let currentIndex = this.heap.length - 1;
		let parentIndex = Math.floor(currentIndex / 2);

		while (parentIndex !== 0 && this.heap[parentIndex] < value) {
			const temp = this.heap[parentIndex];
			this.heap[parentIndex] = value;
			this.heap[currentIndex] = temp;
			currentIndex = parentIndex;
			parentIndex = Math.floor(currentIndex / 2);
		}
	}
}

const heap = new MaxHeap();
heap.insert(45);
heap.insert(36);
heap.insert(54);
heap.insert(27);
heap.insert(64);
console.log(heap.heap); // [null, 64, 54, 45, 27, 36]

요소 제거

class MaxHeap {
	constructor() {
		this.heap = [null];
	}

	remove() {
		const returnValue = this.heap[1];
		this.heap[1] = this.heap.pop();

		let currentIndex = 1;
		let leftIndex = 2;
		let rightIndex = 3;

		while (
			this.heap[currentIndex] < this.heap[leftIndex] ||
			this.heap[currentIndex] < this.heap[rightIndex]
		) {
			if (this.heap[leftIndex] < this.heap[rightIndex]) {
				const temp = this.heap[currentIndex];
				this.heap[currentIndex] = this.heap[rightIndex];
				this.heap[rightIndex] = temp;
				currentIndex = rightIndex;
			} else {
				const temp = this.heap[currentIndex];
				this.heap[currentIndex] = this.heap[leftIndex];
				this.heap[leftIndex] = temp;
				currentIndex = leftIndex;
			}
			leftIndex = currentIndex * 2;
			rightIndex = currentIndex * 2 + 1;
		}

		return returnValue;
	}
}

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스