힙(Heap)는 어떤 자료구조인가?
힙은 부모가 자식보다 항상 크거나 작도록 정렬된 완전 이진 트리이다.
여기서 완전 이진 트리란 트리의 단말 노드를 제외하고 값이 모두 채워진 이진 트리를 의미한다. (이진 트리는 한 부모당 항상 2개의 자식이 존재하는 트리이다.)
부모가 자식보다 항상 큰 힙은 최대 힙(MaxHeap)이라 부르고, 부모가 자식보다 항상 작은 힙은 최소 힙(MinHeap)이라 부른다.
최대힙
최소힙
이때 유의할 점은 힙이 전체가 정렬되어 있지는 않고 일부만 정렬된 상태라는 것이다.
위의 최소힙에서 단말 노드를 보면 8, 10, 9로 오름차순으로 정렬되어 있지 않은 것을 볼 수 있다.
힙은 언제 쓰이는가?
힙은 우선순위 큐를 구현하기 위해 많이 쓰인다.
우선순위 큐는 우선순위가 높은 요소가 항상 먼저 나오는 규칙을 가지고 있고, 아래 3가지의 메서드를 필요로 한다.
- 값 추가
- 우선순위 높은 값 제거
- 우선순위 높은 값 출력
힙은 추가와 제거 시에 동일하게 O(logN)의 시간복잡도를 가지는 가장 효율적인 방식이기 때문에 우선순위 큐를 구현하기 위한 자료구조로 많이 쓰인다.
이를 이용해 최대/최소 값을 빠르게 구하거나 가중치에 따른 최단 거리 문제를 풀 수 있다.
힙은 어떻게 구현할 수 있는가?
힙은 배열을 이용해 구현할 수 있다.
값을 추가할 때는 가장 마지막에 추가를 해주고, 부모와 비교하며 정렬해준다.(bubbleUp)
이때 부모의 인덱스는 Math.floor(idx - 1 / 2)가 된다.
값을 제거할 때는 가장 위의 값(우선순위 높은 값)을 제거해주고, 자식과 비교하며 정렬해준다.(bubbleDown)
이때 자식은 왼쪽, 오른쪽 2개가 있기 때문에 둘 중 더 작은 값과 자리를 바꾸어준다.
왼쪽 자식의 인덱스는 idx * 2 + 1, 오른쪽 자식의 인덱스는 idx * 2 + 2가 된다.
아래에서는 heap에 [node, cost]로 각 노드의 식별자와 가중치를 함께 저장하는 방식으로 구현되어 있다. (가중치가 없을 경우 node만 저장하면 된다.)
필요한 메서드는 아래와 같다.
- 사이즈(size)
- 자리 바꾸기(swap)
- 값 추가하기(add)
- 값 위로 정렬하기(bubbleUp)
- 값 제거하기(poll)
- 값 아래로 정렬하기(bubbbleDown)
- 우선순위 높은 값 출력(peek)
최소 힙
class MinHeap{
constructor(){
this.heap = [];
}
size(){
return this.heap.length;
}
swap(idx1, idx2){
[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]
}
add(val){
this.heap.push(val)
this.bubbleUp()
}
poll(){
if(this.size() === 1) return this.heap.pop()
let val = this.heap[0]
this.heap[0] = this.heap.pop()
this.bubbleDown()
return val
}
bubbleUp(){
let idx = this.size() - 1;
let parentIdx = Math.floor((idx - 1) / 2);
while(this.heap[parentIdx] && this.heap[idx][1] < this.heap[parentIdx][1]){
this.swap(idx, parentIdx);
idx = parentIdx;
parentIdx = Math.floor((idx - 1) / 2)
}
}
bubbleDown(){
let idx = 0;
let leftChildIdx = idx * 2 + 1;
let rightChildIdx = idx * 2 + 2;
while((this.heap[leftChildIdx] && this.heap[idx][1] > this.heap[leftChildIdx][1]) || (this.heap[rightChildIdx] && this.heap[idx][1] > this.heap[rightChildIdx][1])){
let smallestIdx = leftChildIdx;
if(this.heap[rightChildIdx] && this.heap[rightChildIdx][1] < this.heap[leftChildIdx][1]){
smallestIdx = rightChildIdx
}
this.swap(idx, smallestIdx)
idx = smallestIdx;
leftChildIdx = idx * 2 + 1;
rightChildIdx = idx * 2 + 2;
}
}
peek(){
return this.heap[0]
}
}
const minHeap = new MinHeap()
minHeap.add([1, 1])
minHeap.add([2, 2])
minHeap.add([3, 4])
minHeap.add([4, 3])
console.log(minHeap.poll()) // [ 1, 1 ]
console.log(minHeap.poll()) // [ 2, 2 ]
console.log(minHeap.poll()) // [ 4, 3 ]
console.log(minHeap.poll()) // [ 3, 4 ]최대 힙
최대 힙은 최소 힙에서 부등호 방향만 조절해주면 된다.
class MaxHeap{
constructor(){
this.heap = [];
}
size(){
return this.heap.length;
}
swap(idx1, idx2){
[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]
}
add(val){
this.heap.push(val)
this.bubbleUp()
}
poll(){
if(this.size() === 1) return this.heap.pop()
let val = this.heap[0]
this.heap[0] = this.heap.pop()
this.bubbleDown()
return val
}
bubbleUp(){
let idx = this.size() - 1;
let parentIdx = Math.floor((idx - 1) / 2);
while(this.heap[parentIdx] && this.heap[idx][1] > this.heap[parentIdx][1]){
this.swap(idx, parentIdx);
idx = parentIdx;
parentIdx = Math.floor((idx - 1) / 2)
}
}
bubbleDown(){
let idx = 0;
let leftChildIdx = idx * 2 + 1;
let rightChildIdx = idx * 2 + 2;
while((this.heap[leftChildIdx] && this.heap[idx][1] < this.heap[leftChildIdx][1]) || (this.heap[rightChildIdx] && this.heap[idx][1] < this.heap[rightChildIdx][1])){
let biggestIdx = leftChildIdx;
if(this.heap[rightChildIdx] && this.heap[rightChildIdx][1] > this.heap[leftChildIdx][1]){
biggestIdx = rightChildIdx
}
this.swap(idx, biggestIdx)
idx = biggestIdx;
leftChildIdx = idx * 2 + 1;
rightChildIdx = idx * 2 + 2;
}
}
peek(){
return this.heap[0]
}
}
const maxHeap = new MaxHeap()
maxHeap.add([1, 1])
maxHeap.add([2, 2])
maxHeap.add([3, 4])
maxHeap.add([4, 3])
console.log(maxHeap.poll()) // [ 3, 4 ]
console.log(maxHeap.poll()) // [ 4, 3 ]
console.log(maxHeap.poll()) // [ 2, 2 ]
console.log(maxHeap.poll()) // [ 1, 1 ]관련 문제 풀어보기
[백준] 최대 힙
- 난이도 : 실버 2
- 문제 링크 : https://www.acmicpc.net/problem/11279
여기서는 가중치가 없으므로 실제 값만 저장해주면 된다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0];
class MaxHeap{
constructor(){
this.heap = [];
}
size(){
return this.heap.length;
}
swap(idx1, idx2){
[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]
}
add(val){
this.heap.push(val)
this.bubbleUp()
}
poll(){
if(this.size() === 0) return 0
if(this.size() === 1) return this.heap.pop()
let val = this.heap[0]
this.heap[0] = this.heap.pop()
this.bubbleDown()
return val
}
bubbleUp(){
let idx = this.size() - 1;
let parentIdx = Math.floor((idx - 1) / 2);
while(parentIdx >= 0 && this.heap[idx] > this.heap[parentIdx]){
this.swap(idx, parentIdx);
idx = parentIdx;
parentIdx = Math.floor((idx - 1) / 2)
}
}
bubbleDown(){
let idx = 0;
let leftChildIdx = idx * 2 + 1;
let rightChildIdx = idx * 2 + 2;
while((leftChildIdx < this.size() && this.heap[idx] < this.heap[leftChildIdx] || (rightChildIdx < this.size() && this.heap[idx] < this.heap[rightChildIdx]))){
let biggestIdx = leftChildIdx;
if(rightChildIdx < this.size() && this.heap[rightChildIdx] > this.heap[leftChildIdx]){
biggestIdx = rightChildIdx
}
this.swap(idx, biggestIdx)
idx = biggestIdx;
leftChildIdx = idx * 2 + 1;
rightChildIdx = idx * 2 + 2;
}
}
}
const maxHeap = new MaxHeap();
const answer = [];
for(let i=1;i<=N;i++){
let v = +input[i]
if(v === 0){
answer.push(maxHeap.poll())
}else{
maxHeap.add(v)
}
}
console.log(answer.join('\n'))[백준] 카드 정렬하기
- 난이도 : 골드 4
- 문제 링크 : https://www.acmicpc.net/problem/1715
- 일단 모든 값을 최소 힙에 넣기
- 힙에 요소가 2개 이상있으면 아래 단계를 반복
- 맨 위 2개를 꺼내서 합하기 (sum)
- 합한 값을 전역 변수에 더하기 (answer += sum)
- 그 값을 다시 최소 힙에 넣기 (minHeadp.add(sum))
주의
처음에 while 조건을 minHeap.size() > 0 으로 해서 카드가 하나만 남았을 때도 더하도록 해서 틀렸다. 카드가 하나만 남았을 때는 합칠 필요가 없으므로 카드가 2개 이상 남았을 때만 반복하도록 해야 한다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0];
class MinHeap{
constructor(){
this.heap = [];
}
size(){
return this.heap.length;
}
swap(idx1, idx2){
[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]
}
add(val){
this.heap.push(val)
this.bubbleUp()
}
poll(){
if(this.size() === 0) return 0;
if(this.size() === 1) return this.heap.pop()
let val = this.heap[0]
this.heap[0] = this.heap.pop()
this.bubbleDown()
return val
}
bubbleUp(){
let idx = this.size() - 1;
let parentIdx = Math.floor((idx - 1) / 2);
while(this.heap[parentIdx] && this.heap[idx] < this.heap[parentIdx]){
this.swap(idx, parentIdx);
idx = parentIdx;
parentIdx = Math.floor((idx - 1) / 2)
}
}
bubbleDown(){
let idx = 0;
let leftChildIdx = idx * 2 + 1;
let rightChildIdx = idx * 2 + 2;
while((this.heap[leftChildIdx] && this.heap[idx] > this.heap[leftChildIdx]) || (this.heap[rightChildIdx] && this.heap[idx] > this.heap[rightChildIdx])){
let smallestIdx = leftChildIdx;
if(this.heap[rightChildIdx] && this.heap[rightChildIdx] < this.heap[leftChildIdx]){
smallestIdx = rightChildIdx
}
this.swap(idx, smallestIdx)
idx = smallestIdx;
leftChildIdx = idx * 2 + 1;
rightChildIdx = idx * 2 + 2;
}
}
}
const minHeap = new MinHeap();
let answer = 0;
for(let i=1;i<=N;i++){
let v = +input[i];
minHeap.add(v)
}
while(minHeap.size() > 1){
let v1 = minHeap.poll();
let v2 = minHeap.poll();
let sum = v1 + v2;
answer += sum;
minHeap.add(sum)
}
console.log(answer)[백준] 가운데를 말해요
- 난이도 : 골드 2
- 문제 링크 : https://www.acmicpc.net/problem/1655
이 문제는 두 개의 힙을 이용해 풀 수 있다.
오름차순으로 정렬된 수열을 절반으로 나눈다고 가정할 때, 작은 값들을 최대 힙에 저장하고 큰 값들을 최소 힙에 저장해둔다. (일단 최대 힙에 값을 넣고, 그중 가장 큰 값을 최소 힙에 넣기)
이때, 최대 힙의 개수가 최소 힙 개수와 같거나 1개만 크도록 유지하면 최대 힙의 가장 큰 값이 바로 중간값이 된다.
주의
가중치를 저장 안하고 쓸 때는parentIdx >= 0처럼 인덱스 범위로 체크해야한다.
!this.heap[parentIdx]로 하면 0일 경우에 false가 되서 제대로 체크가 안 되는 문제가 발생한다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0];
class MinHeap{
constructor(){
this.heap = [];
}
size(){
return this.heap.length;
}
swap(idx1, idx2){
[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]
}
add(val){
this.heap.push(val)
this.bubbleUp()
}
poll(){
if(this.size() === 0) return 0;
if(this.size() === 1) return this.heap.pop()
let val = this.heap[0]
this.heap[0] = this.heap.pop()
this.bubbleDown()
return val
}
bubbleUp(){
let idx = this.size() - 1;
let parentIdx = Math.floor((idx - 1) / 2);
while(parentIdx >= 0 && this.heap[idx] < this.heap[parentIdx]){
this.swap(idx, parentIdx);
idx = parentIdx;
parentIdx = Math.floor((idx - 1) / 2)
}
}
bubbleDown(){
let idx = 0;
let leftChildIdx = idx * 2 + 1;
let rightChildIdx = idx * 2 + 2;
while((leftChildIdx < this.size() && this.heap[idx] > this.heap[leftChildIdx]) || (rightChildIdx < this.size() && this.heap[idx] > this.heap[rightChildIdx])){
let smallestIdx = leftChildIdx;
if(rightChildIdx < this.size() && this.heap[rightChildIdx] < this.heap[leftChildIdx]){
smallestIdx = rightChildIdx
}
this.swap(idx, smallestIdx)
idx = smallestIdx;
leftChildIdx = idx * 2 + 1;
rightChildIdx = idx * 2 + 2;
}
}
peek(){
return this.heap[0]
}
}
class MaxHeap{
constructor(){
this.heap = [];
}
size(){
return this.heap.length;
}
swap(idx1, idx2){
[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]
}
add(val){
this.heap.push(val)
this.bubbleUp()
}
poll(){
if(this.size() === 0) return 0;
if(this.size() === 1) return this.heap.pop()
let val = this.heap[0]
this.heap[0] = this.heap.pop()
this.bubbleDown()
return val
}
bubbleUp(){
let idx = this.size() - 1;
let parentIdx = Math.floor((idx - 1) / 2);
while(parentIdx >= 0 && this.heap[idx] > this.heap[parentIdx]){
this.swap(idx, parentIdx);
idx = parentIdx;
parentIdx = Math.floor((idx - 1) / 2)
}
}
bubbleDown(){
let idx = 0;
let leftChildIdx = idx * 2 + 1;
let rightChildIdx = idx * 2 + 2;
while((leftChildIdx < this.size() && this.heap[idx] < this.heap[leftChildIdx]) || (rightChildIdx < this.size() && this.heap[idx] < this.heap[rightChildIdx])){
let biggestIdx = leftChildIdx;
if(rightChildIdx < this.size() && this.heap[rightChildIdx] > this.heap[leftChildIdx]){
biggestIdx = rightChildIdx
}
this.swap(idx, biggestIdx)
idx = biggestIdx;
leftChildIdx = idx * 2 + 1;
rightChildIdx = idx * 2 + 2;
}
}
peek(){
return this.heap[0]
}
}
const minHeap = new MinHeap();
const maxHeap = new MaxHeap();
let answer = [];
for(let i=1;i<=N;i++){
let v = +input[i];
maxHeap.add(v);
minHeap.add(maxHeap.poll());
if(maxHeap.size() < minHeap.size()){
maxHeap.add(minHeap.poll())
}
answer.push(maxHeap.peek())
}
console.log(answer.join('\n'))
모든게 새롭고 재밌는 프론트엔드 새싹