[자료구조] 힙(Heap)

최댓값 혹은 최솟값을 빠르게 찾기 위해 완전이진트리 형태로 연산을 수행하는 자료구조

힙 대표 속성

• 정렬 : 각 노드의 값은 자식 노드가 가진 값보다 작거나 혹은 큰 순서대로 정렬
• 형태 : 트리의 형태는 완전이진트리(complete binary tree) 모양

힙 종류

• 최소 힙(Min Heap) : 부모 노드의 값이 자식 노드의 값보다, 작거나 같은 완전 이진 트리
• 최대 힙(Max Heap) : 부모 노드의 값이 자식 노드의 값보다, 크거나 같은 완전 이진 트리
  

힙 구현

• 완전 이진 트리 성질을 만족하기 때문에 1차원 배열로 표현 가능
• 현재 노드 : N, 부모 노드 : (N-1)/2, 왼쪽 자식 노드 : (N2)+1, 오른쪽 자식 노드 : (N2)+2

구현 메서드(method)

• 노드 위치 계산 : Heap.parentIndex(), Heap.leftChildIndex(), Heap.rightChildIndex()
• 노드 값 확인 : Heap.parent(), Heap.leftChild(), Heap.rightChild()
• 노드 추가/삭제(추출) : Heap.insert(), Heap.bubbleUp(), Heap.extract(), Heap.bubbleDown()

최소힙

// 최소 힙(MinHeap)
// Heap() : 배열 내 요소를 저장하기 위한 생성자
function Heap() {
  this.items = [];
}

// swap() : 배열 내 두 요소 위치 변경
Heap.prototype.swap = function (index1, index2) {
  let tmp = this.items[index1];
  this.items[index1] = this.items[index2];
  this.items[index2] = tmp;
};

// parentIndex() : 부모 노드의 위치 반환
Heap.prototype.parentIndex = function (index) {
  return Math.floor((index - 1) / 2);
};

// leftChildIndex() : 왼쪽 자식 노드의 위치 반환
Heap.prototype.leftChildIndex = function (index) {
  return index * 2 + 1;
};

// rightChildIndex() : 오른쪽 자식 노드의 위치 반환
Heap.prototype.rightChildIndex = function (index) {
  return index * 2 + 2;
};

// parent() : 부모 노드의 요소값 반환
Heap.prototype.parent = function (index) {
  return this.items[this.parentIndex(index)];
};

// leftChild() : 왼쪽 자식 노드의 요소 값 반환
Heap.prototype.leftChild = function (index) {
  return this.items[this.leftChildIndex(index)];
};

// rightChild() : 오른족 자식 노드의 요소 값 반환
Heap.prototype.rightChild = function (index) {
  return this.items[this.rightChildIndex(index)];
};

// peak() : 현재 정렬된 최소/최대 요소값 반환
Heap.prototype.peak = function () {
  return this.items[0];
};

// size() : 현재 배열 내 크기 반환
Heap.prototype.size = function () {
  return this.items.length;
};

// insert() : 신규 노드 추가
Heap.prototype.insert = function (item) {
  this.items[this.size()] = item;
  this.bubbleUp();
};

// bubbleUp() : 추가된 노드 위치 정렬
Heap.prototype.bubbleUp = function () {
  let index = this.size() - 1;
  // 부모 노드와 비교하면서 정렬
  // 부모가 있는지부터 확인
  while (this.parent(index) && this.parent(index) > this.items[index]) {
    this.swap(this.parentIndex(index), index);
    index = this.parentIndex(index);
  }
};

// extract() : root 노드 반환 및 삭제
Heap.prototype.extract = function () {
  let item = this.items[0];
  this.items[0] = this.items[this.size() - 1];
  this.items.pop(); // 배열의 마지막 요소를 없애 준다.
  this.bubbleDown();
  return item;
};

// bubbleDown() : 대체된 root 노드 위치 정렬 -> 위에서 부터 수행(root 부터) -> 내려가면서 왼쪽 오른쪽 노드 둘다 확인
Heap.prototype.bubbleDown = function () {
  let index = 0;
  while (
    this.leftChild(index) &&
    (this.leftChild(index) < this.items[index] ||
      this.rightChild(index) < this.items[index])
  ) {
    let childIndex = this.leftChildIndex(index);
    if (
      this.rightChild(index) &&
      this.rightChild(index) < this.items[childIndex]
    ) {
      childIndex = this.rightChildIndex(index);
    }
    this.swap(childIndex, index);
    index = childIndex;
  }
};

let minHeap = new Heap();
minHeap.insert(90);
minHeap.insert(15);
minHeap.insert(10);
minHeap.insert(7);
minHeap.insert(12);
minHeap.insert(2);
minHeap.insert(8);
minHeap.insert(3);
// console.log(minHeap);
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
// console.log(minHeap);

----------------------------------------------------------
OUTPUT
2
3
7
8
10
12
15
90

최대값

최소값 bubbleUp(), bubbleDown() 코드에 있는 조건문의 부등호를 반대로 바꾸면 된다

// 최대 힙(MaxHeap)
// Heap() : 배열 내 요소를 저장하기 위한 생성자
function Heap() {
  this.items = [];
}

// swap() : 배열 내 두 요소 위치 변경
Heap.prototype.swap = function (index1, index2) {
  let tmp = this.items[index1];
  this.items[index1] = this.items[index2];
  this.items[index2] = tmp;
};

// parentIndex() : 부모 노드의 위치 반환
Heap.prototype.parentIndex = function (index) {
  return Math.floor((index - 1) / 2);
};

// leftChildIndex() : 왼쪽 자식 노드의 위치 반환
Heap.prototype.leftChildIndex = function (index) {
  return index * 2 + 1;
};

// rightChildIndex() : 오른쪽 자식 노드의 위치 반환
Heap.prototype.rightChildIndex = function (index) {
  return index * 2 + 2;
};

// parent() : 부모 노드의 요소값 반환
Heap.prototype.parent = function (index) {
  return this.items[this.parentIndex(index)];
};

// leftChild() : 왼쪽 자식 노드의 요소 값 반환
Heap.prototype.leftChild = function (index) {
  return this.items[this.leftChildIndex(index)];
};

// rightChild() : 오른족 자식 노드의 요소 값 반환
Heap.prototype.rightChild = function (index) {
  return this.items[this.rightChildIndex(index)];
};

// peak() : 현재 정렬된 최소/최대 요소값 반환
Heap.prototype.peak = function () {
  return this.items[0];
};

// size() : 현재 배열 내 크기 반환
Heap.prototype.size = function () {
  return this.items.length;
};

// insert() : 신규 노드 추가
Heap.prototype.insert = function (item) {
  this.items[this.size()] = item;
  this.bubbleUp();
};

// bubbleUp() : 추가된 노드 위치 정렬
Heap.prototype.bubbleUp = function () {
  let index = this.size() - 1;
  // 부모 노드와 비교하면서 정렬
  // 부모가 있는지부터 확인
  while (this.parent(index) && this.parent(index) < this.items[index]) {
    this.swap(this.parentIndex(index), index);
    index = this.parentIndex(index);
  }
};

// extract() : root 노드 반환 및 삭제
Heap.prototype.extract = function () {
  let item = this.items[0];
  this.items[0] = this.items[this.size() - 1];
  this.items.pop(); // 배열의 마지막 요소를 없애 준다.
  this.bubbleDown();
  return item;
};

// bubbleDown() : 대체된 root 노드 위치 정렬 -> 위에서 부터 수행(root 부터) -> 내려가면서 왼쪽 오른쪽 노드 둘다 확인
Heap.prototype.bubbleDown = function () {
  let index = 0;
  while (
    this.leftChild(index) &&
    (this.leftChild(index) > this.items[index] ||
      this.rightChild(index) > this.items[index])
  ) {
    let childIndex = this.leftChildIndex(index);
    if (
      this.rightChild(index) &&
      this.rightChild(index) > this.items[childIndex]
    ) {
      childIndex = this.rightChildIndex(index);
    }
    this.swap(childIndex, index);
    index = childIndex;
  }
};

let minHeap = new Heap();
minHeap.insert(90);
minHeap.insert(15);
minHeap.insert(10);
minHeap.insert(7);
minHeap.insert(12);
minHeap.insert(2);
minHeap.insert(8);
minHeap.insert(3);
// console.log(minHeap);
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
// console.log(minHeap);

----------------------------------------------------------
OUTPUT
90
15
12
10
8
7
3
2