[JS] 힙 (Heap)

1. 힙 (Heap)

 힙은 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조다. 키 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙이라고 하고, 키 값이 작은 노드를 찾기 위한 힙을 최소 힙이라고 한다. 

 

 

 최대 힙은 부모노드의 키 값 > 자식노드의 키 값의 관계를 가지는 완전 이진 트리다. 따라서 최대 힙의 루트 노드는 가장 큰 값이 된다. 하지만 최소 힙은 부모노드의 키 값 < 자식노드의 키 값의 관계를 가지며 최소 힙의 루트 노드는 가장 작은 값이 된다. 일반적으로 힙은 최대 힙을 의미하며, 같은 키 값의 노드가 중복될 수 있다.

 

 

 따라서 힙이 되려면 두 가지 조건을 만족해야한다.

• (1) 완전 이진 트리여야 한다.

• (2) 부모노드의 키 값 > 자식노드의 키 값 또는 부모노드의 키 값 < 자식노드의 키 값의 관계를 가져야한다.
  
  

[그림 1] 힙과 힙이 아닌 트리들 

 

2. 힙의 삽입 연산

 힙에서의 삽입 연산을 할 때 가장 중요한 것은 완전 이진 트리를 유지해야한다는 것이다. 그러기 위해서 먼저, 마지막 노드의 다음 자리를 확장하여 만든 자리에 삽입할 노드를 임시로 저장해야한다.

 

[그림 2] 마지막 노드 자리의 다음 자리에 삽입할 노드를 임시로 저장

 

그 다음에는 키 값의 관계가 최대 힙이 되도록 재구성하기 위해 삽입한 노드의 키 값과 부모노드의 키 값을 비교한다.

 

[그림 3] 힙에 맞는 조건을 이용하여 키 값의 위치를 조절한다.

 

3. 힙의 삭제 연산

힙에서의 삭제 연산은 언제나 루트 노드에 있는 원소를 삭제하여 반환한다. 따라서 최대 힙에서는 가장 큰 원소를 삭제하여 반환하고, 최소 힙에서는 가장 작은 원소를 삭제하여 반환한다. 그런데 중요한 것은 힙의 삭제연산에서도 완전 이진 트리의 조건과 각 힙의 맞는 조건을 유지해야한다는 것이다. 방법은 다음과 같다.

 

 

 먼저 루트의 원소를 삭제한다.

 

[그림 4] 루트 노드를 삭제

 

 마지막 노드의 값을 루트 노드의 값에 넣고 마지막 노드를 삭제한다.

 

[그림 5] 마지막 노드 값을 루트 노드에 넣고, 마지막 노드 삭제

 

 자리를 바꿔가며 가장 큰 수가 루트노드로 오게 한다.

 

[그림 6] 가장 큰 수를 루트 노드에 오도록 자리를 계속 바꿔준다.

 

4. 프로그램 코드

 코드는 다음과 같다. 책에서는 순차 자료구조 방식을 이용하면 배열 인덱스의 관계를 바탕으로 부모노드를 쉽게 찾을 수 있는 장점 때문에 배열을 이용해서 힙을 표현했다. 나도 책의 방법을 따라 순차 자료구조 방식을 이용했다.

const Heap = function Heap(){
  this.heap = Array(30).fill('');
  this.heapSize = 0;
}

Heap.prototype.insertHeap = function(data){
  const heap = this.heap;
  const newData = data;
  if(this.heapSize === 0){
    heap[1] = newData;
    this.heapSize++;
  }
  else{
    this.heapSize++;
    let idx = this.heapSize;

    heap[idx] = newData;
    
    //데이터를 넣었으면 비교 연산을 한다.
    let parentIdx = parseInt(idx/2);

    while(parentIdx > 0){
      if(heap[parentIdx] < heap[idx]){
        let temp = heap[parentIdx];
        heap[parentIdx] = heap[idx];
        heap[idx] = temp;
      }
      else
        break;
      parentIdx = parseInt(parentIdx/2);
    }
  }
};

Heap.prototype.printAll = function(){
  let result = '';
  for(let i=1; i<=this.heapSize; i++)
    result += `${this.heap[i]} `
  console.log("출력:",result);
}

Heap.prototype.deleteHeap = function(){
  const lastIdx = this.heapSize;
  const heap = this.heap;
  const deleteVal = heap[1]; 
  let idx = 1;
  console.log(heap);
  heap[1] = heap[lastIdx];
  heap[lastIdx] = '';

  while(heap[idx*2] !== '' && heap[idx*2+1] !== ''){
    let temp = 0;
    if(heap[idx] < heap[idx*2]){
      temp = heap[idx];
      heap[idx] = heap[idx*2];
      heap[idx*2] = temp;
      idx *= 2;
    }
    else if(heap[idx] < heap[idx*2+1]){
      temp = heap[idx];
      heap[idx] = heap[idx*2+1];
      heap[idx*2+1] = temp;
      idx = idx*2+1;  
    }
    else{
      break;
    }
  } 

  console.log(`${deleteVal} 삭제 완료!`);
}


function main(){
  const heap = new Heap();
  heap.insertHeap(23);
  heap.insertHeap(19);
  heap.insertHeap(15);
  heap.insertHeap(8);
  heap.insertHeap(13);
  heap.insertHeap(10);

  heap.deleteHeap();
  heap.printAll();
}

main();

5. 참고자료

 자바로 배우는 쉬운 자료구조, 한빛 아카데미