힙

1. 힙이란?

• O(1) 시간에 가장 높은 항목이나 가장 낮은 항목을 반환하는 중요한 자료구조.
• 힙은 트리와 비슷한 자료 구조의 일종
• 최대 힙의 경우 부모가 자식보다 크고, 최소 힙의 경우 부모가 자식보다 작음
• 다른 자료 구조와 달리 자식에 대한 포인터를 갖는 대신에 배열을 사용해 자료를 저장.
• 배열에서 힙 노드의 자식 위치(인덱스)를 쉽게 계산할 수 있음
• 힙을 사용하면 부모와 자식 간의 관계를 쉽게 정의할 수 있기 때문

2. 이진 힙

• 배열을 사용해 자료를 저장하기 때문에 배열의 인덱스는 각 항목의 차수/높이를 정의
• 첫 번째 배열 항목을 루트로 설정한 다음 각 왼쪽 항목과 오른쪽 항목을 순서대로 채움으로써 이진 힙을 만들 수 있음.
  
• 이진 힙의 종류: 최대 힙, 최소 힙
  • 최대 힙: 루트노드가 가장 높은 값을 갖고 각 노드이 값이 자식의 값보다 큼
    
  • 최소 힙: 루트 노드가 가장 낮은 값을 갖고 각 노드의 값이 자식의 값 보다 작음
• 힙은 문자열과 정수, 사용자의 정의 크랠스와 같이 어떤 종류의 값이든 저장할 수 있음

3. 이진 힙 배열 인덱스 구조

• 이진 힙의 경우 힙을 나타내기 위해 배열이 사용되는데 다믕과 같이 인덱스를 사용함

  노드	인덱스
  (자신)	N
  부모	(N-1)/2
  왼쪽 자식	(N*2)+1
  오른쪽 자식	(N*2)+2

  - N은 노드의 인덱스
• 힙에서 인덱스를 사용하여 부모-자식 간의 관계
  
• 일반적인 Heap Code

function Heap() {
  this.items = [];
}

Heap.prototype.swap = function(idx1, idx2) {
  let tmp = this.items[idx1];
  this.items[idx1] = this.items[idx2];
  this.items[idx2] = tmp;
}

Heap.prototype.parentIdx = function(idx) {
  return Math.floor((idx-1)/2);
}

Heap.prototype.leftChildIdx = function(idx) {
  return idx*2+1;
}

Heap.prototype.rightChildIdx = function(idx) {
  return idx*2+1;
}

Heap.prototype.parent = function(idx) {
  return this.items[this.parentIdx(idx)];
}

Heap.prototype.left = function(idx) {
  return this.items[this.leftChildIdx(idx)];
}

Heap.prototype.right = function(idx) {
  return this.items[this.rightChildIdx(idx)];
}

Heap.prototype.peek = function(item) {
  return this.items[0]; 
}

Heap.prototype.size = function() {
  return this.items.length;
}

3-1. 최소힙

• 삼투: 과학시간에 배웠던 것으로 농도가 높은 건 아래로, 낮은 건 위로 가는 현상인데, 최소힙의 자료 구조도 이와 비슷하다
• 항목을 추가하거나 삭제할 때 힙의 구조가 유지되야 함.(최대 힙의 경우 노드가 자식보다 커야 하고 최소 힙의 경우 노드가 자식보다 작아야 함)
• 최소힙의 시간 복잡도는 O(log2(N))
• [12,2,23,4,13]의 배열을 최소 힙에 삽입해 보면
  
• 최소힙 구현

function MinHeap() {
  this.items=[];
}

// 프로토타입을 복사함으로써 Heap클래스의 함수를 사용할수 있음
MinHeap.prototype = Object.create(Heap.prototype);

// Heap의 요소 추가
MinHeap.prototype.add = function(item) {
  this.items[this.items.length] = item;
  this.bubbleUp();
}

// 루트 노드를 제거하고 제거한 루트노드의 값을 반환하며, 최소 힙 순서를 유지하는 함수
MinHeap.prototype.poll = function() {
  // 루트 노드의 값을 변수에 할당
  let item = this.items[0];
  this.items[0] = this.items[this.items.length-1];
  this.items.pop();
  this.bubbleDown();
  return item;
}

// 루트노드를 제거했을때 다시 최소힙의 순서를 유지하게 하는 함수
MinHeap.prototype.bubbleDown = function() {
  let idx = 0;
  // 왼쪽 자식의 노드가 존재하고, 왼쪽 자식노드의 값이 최소힙의 인덱스에 해당하는 노드의 값보다 작다면
  while(this.leftChild(idx) && this.leftChild(idx) < this.items[idx] || this.rightChild(idx) < this.items[idx]) {
    // 왼쪽 자식노드의 값을 변수에 할당
    let smallerIdx = this.leftChildIdx(idx);
    // 만일 오른쪽 자식노드의 값이 존재하고, 오른쪽 자식의 노드의 값이 최소힙의 smallerIdx 해당하는 노드의 값보다 작다면
    if(this.rightChild(idx) && this.rightChild(idx) < this.items[smallerIdx]) {
      smallerIdx = this.rightChildIdx(idx);
    }
    // 해당 인덱스의 노드를 스왑
    this.swap(smallerIdx, idx);
    idx = smallerIdx;
  }
}
// 노드를 추가했을 시 자식노드의 값과 부모 노드의 값을 비교하여 최소힙 순서 유지
MinHeap.prototype.bubbleUp = function() {
  // 가장 마지막 노드의 인덱스값
  let idx = this.items.length-1;
  // 부모노드의 값이 존재하고, 부모노드의 값이 추가된 노드의 값보다 크면
  while(this.parent(idx) && this.parent(idx) > this.items[idx]) {
    // 부모노드의 값과 자식의 노드의 값 스왑
    this.swap(this.parentIdx(idx), idx);
    // 인덱스 변수에 부모노드의 인덱스 할당
    idx = this.parentIdx(idx);
  }
}

let mh = new MinHeap();
mh.add(1);
mh.add(10);
mh.add(5);
mh.add(100);
mh.add(8);

console.log(mh.poll()); // 1
console.log(mh.poll()); // 5
console.log(mh.poll()); // 8
console.log(mh.poll()); // 10
console.log(mh.poll()); // 100

3-2. 최대힙

• [12,2,23,4,13]를 최대힙 구조로 만들 때
  
  최종결과는 [23,13,12,2,4]
• 최대힙 구현

function MaxHeap() {
  this.items=[];
}

MaxHeap.prototype = Object.create(Heap.prototype);

// Heap의 요소 추가
MaxHeap.prototype.add = function(item) {
  this.items[this.items.length] = item;
  this.bubbleUp();
}

// 루트 노드를 제거하고 제거한 루트노드의 값을 반환하며, 힙 순서를 유지하는 함수
MaxHeap.prototype.poll = function() {
  // 루트 노드의 값을 변수에 할당
  let item = this.items[0];
  this.items[0] = this.items[this.items.length-1];
  this.items.pop();
  this.bubbleDown();
  return item;
}

MaxHeap.prototype.bubbleDown = function() {
  let idx = 0;
  // 왼쪽 자식의 노드가 존재하고, 왼쪽 자식노드의 값이 최대힙의 인덱스에 해당하는 노드의 값보다 크다면
  while(this.leftChild(idx) && this.leftChild(idx) > this.items[idx] || this.rightChild(idx) > this.items[idx]) {
    // 왼쪽 자식노드의 값을 변수에 할당
    let biggerIdx = this.leftChildIdx(idx);
    // 만일 오른쪽 자식노드의 값이 존재하고, 오른쪽 자식의 노드의 값이 최소힙의 smallerIdx 해당하는 노드의 값보다 작다면
    if(this.rightChild(idx) && this.rightChild(idx) > this.items[biggerIdx]) {
      biggerIdx = this.rightChildIdx(idx);
    }
    // 해당 인덱스의 노드를 스왑
    this.swap(biggerIdx, idx);
    idx = biggerIdx;
  }
}
// 노드를 추가했을 시 자식노드의 값과 부모 노드의 값을 비교하여 최소힙 순서 유지
MaxHeap.prototype.bubbleUp = function() {
  // 가장 마지막 노드의 인덱스값
  let idx = this.items.length-1;
  // 부모노드의 값이 존재하고, 부모노드의 값이 추가된 노드의 값보다 크면
  while(this.parent(idx) && this.parent(idx) < this.items[idx]) {
    // 부모노드의 값과 자식의 노드의 값 스왑
    this.swap(this.parentIdx(idx), idx);
    // 인덱스 변수에 부모노드의 인덱스 할당
    idx = this.parentIdx(idx);
  }
}

let mh = new MaxHeap();
mh.add(1);
mh.add(10);
mh.add(5);
mh.add(100);
mh.add(8);

console.log(mh.poll()); // 100
console.log(mh.poll()); // 10
console.log(mh.poll()); // 8
console.log(mh.poll()); // 5
console.log(mh.poll()); // 1