[비선형] 7. 힙

in 자료구조 on 비선형




1. 힙 (Heap)

힙
힙

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


힙 대표 속성

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


힙 종류

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


힙 구현

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


구현 메서드

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



2. 힙 구현하기

기본 메소드 구현

// 최소힙 (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)];
};

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

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



노드 추가 : insert(), bubbleUp()

// 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);
  }
};

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);

console.log(minHeap);
// Heap { items: [
//     2, 10, 7, 90,
//    12, 15, 8
//  ] }

minHeap.insert(3);

console.log(minHeap);
// Heap { items: [
//     2,  3, 7, 10,
//    12, 15, 8, 90
//  ] }



노드 삭제 : extract(), bubbleDown()

// 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 노드 위치를 기준으로 정렬
Heap.prototype.bubbleDown = function () {
  let index = 0;
  while (
    // 완전이진트리이기 때문에 left트가 존재해야지만 right 가 존재한다.
    this.leftChildIndex(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;
  }
};

console.log(minHeap);
// Heap { items: [
//     2,  3, 7, 10,
//    12, 15, 8, 90
//  ] }

console.log(minHeap.extract()) //2
console.log(minHeap)
// Heap { items: [
//     3, 10, 7, 90,
//    12, 15, 8
//  ] }
console.log(minHeap.extract()) //3
console.log(minHeap.extract()) //7
console.log(minHeap.extract()) //8
console.log(minHeap.extract()) //10
console.log(minHeap.extract()) //12
console.log(minHeap.extract()) //15



최대힙 구현하기

// 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);
  }
};

// bubbleDown() : 대체된 root 노드 위치를 기준으로 정렬
Heap.prototype.bubbleDown = function () {
  let index = 0;
  while (
    // 완전이진트리이기 때문에 left트가 존재해야지만 right 가 존재한다.
    this.leftChildIndex(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;
  }
};