Heap 정리

 

힙(heap)이란?

이진트리의 형태를 띄고 있는 자료구조, 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬된다.

우선순위 큐를 구현할때 가장 적합한 자료구조이다. (우선순위 큐에 힙이 포함되는 형태)

 

*Root : 트리에서 최상위 Node

 

힙의 특징 

 

1. 우선순위가 높은 요소가 먼저 나온다.
2. Root가 최대값이 되는 최대 힙(오름차순)과 가장 작은 값(내림차순)이 되는 최소 힙 두가지 있다.  
3. 자바스크립트에서는 직접 구현해야 하는 단점.
4. 완전 이진 트리의 높이는  logN이기 때문에, 노드 추가 삭제시 시간복잡도는  O(logN) 지수시간을 가진다.

*빠름 O(1) < O(logN) < O(N) < O(NlogN) 느림

 

 

힙에서 추가를 구현할때 알고리즘 (최대힙)

1. 새로운 요소를 추가할때는 우선 트리의 가장 마지막 정점(Node)에 위치 시킨다.

2. 추가 후 부모의 정점과 우선순위를 비교한다.

3. 부모의 정점보다 우선순위가 높다면 부모와 서로 순서를 바꾼다.

4. 우선순위가 가장 높은 Root가 정점이 될때까지 반복하여 전부 정렬한다.

 

 

힙에서 삭제를 구현할때 알고리즘 (최대힙)

1. 요소를 제거할때는 항상  Root에서 가져온다(pop).

2. 가장 마지막 정점(Node)를 가져와 Root를 채운다.

3. Root와 자식의 우선순위를 비교한다.

4. Root보다 자식의 우선순위가 높다면 서로 순사를 바꾼다.

5. 모든 정점에서 자식의 우선순위가 낮을 때까지 반복한다.

 

 

//최대힙 구현
class Maxheap {
  constructor() {
    this.heap = [null];
  }

  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);
        
    while (parentIndex !== 0 && this.heap[parentIndex] < value) {
      const temp = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      this.heap[currentIndex] = temp;

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

  pop() {
    if (this.heap.length === 1) return "empty!!"; //다시 push해도 [0]가 비어있도록 바로 리턴시켜서 종료
    if (this.heap.length === 2) return this.heap.pop(); //Node가 하나만 남았을때는 맨뒤 Node를 가져오지 않도록 바로 리턴
    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop(); //맨뒤의 정점을 root로 가져온다. 

    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
        
    while (
      this.heap[currentIndex] < this.heap[leftIndex] ||
      this.heap[currentIndex] < this.heap[rightIndex]
      ) {
        if (this.heap[leftIndex] < this.heap[rightIndex]) {
          const temp = this.heap[currentIndex];
          this.heap[currentIndex] = this.heap[rightIndex];
          this.heap[rightIndex] = temp;
          this.currentIndex = rightIndex;
        } else {
          const temp = this.heap[currentIndex];
          this.heap[currentIndex] = this.heap[leftIndex];
          this.heap[leftIndex] = temp;
          this.currentIdex = leftIndex; 
        }

        leftIndex = currentIndex * 2;
        rightIndex = currentIndex * 2 + 1;
    }

    return returnValue;
  } 
}

const heap = new Maxheap();

heap.push(54);
heap.push(33);
heap.push(44);
heap.push(55);
console.log(heap.heap); //(6) [null, 55, 54, 44, 33, 54]

console.log(heap.pop()); //55
console.log(heap.pop()); //54
console.log(heap.pop()); //54
console.log(heap.pop()); //44
console.log(heap.pop()); //33
console.log(heap.pop()); //empty!! 
console.log(heap.heap); //[null] 

console.log(heap.pop()); //empty!! heap이 전부 비었을때 pop을 하면 "empty" 반환
console.log(heap.heap); //[null]