힙

우선순위 큐(자료구조X, 개념)

FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐

힙 (Heap)

❌ 힙 != 우선순위 큐

• 우선순위가 높은 요소가 먼저 나감
• 루트가 가장 큰 값이 되는 최대힙 / 루트가 가장 작은 값이 되는 최소힙 (오름차순, 내림차순)
• Js에서는 직접 구현해서 사용해야 함
  

Heap 요소 추가

1. 요소 추가: 트리의 가장 마지막 정점에 위치
2. 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꿈
3. 위 과정을 반복 -> 가장 우선순위가 높은 정점이 루트가 됨
4. 완전 이진 트리의 높이는 log N이기에 힙의 요소 추가 알고리즘은 O(log N) 시간복잡도를 가짐

Heap 요소 제거

1. 요소 제거: 루트 정점만 가능
2. 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치함
3. 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꿈
4. 두 자식 정점이 우선순위가 더 낮을 때까지 반복
5. 완전 이진 트리의 높이는 log N이기에 힙의 요소 추가 알고리즘은 O(log N) 시간복잡도를 가짐

코드로 구현

• 왼쪽 자식의 index = 부모 index * 2
• 오른쪽 자식의 index = (부모 index * 2) + 1
• 부모의 index = Math.floor(자식의 인덱스 / 2);

최대 힙(Max Heap)

class MaxHeap {
  // 내부적으로 관리할 배열 생성
  constructor() {
    // 편의성을 위해 0번 인덱스는 null
    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);
	}
  }
}

const heap = new MaxHeap();
heap.push(45);
heap.push(36);
heap.push(54);
heap.push(27);
heap.push(63);
console.log(heap.heap);
// [null, 63, 54, 45, 27, 36]

최소 힙(Min Heap)
우선 순위가 가장 높은 요소를 제거하기
-> 제거한 요소들을 새로운 배열에 추가함으로써
Heap의 우선순위를 나열할 수 있다.

// heap state: [null, 63, 54, 45, 27, 36]

pop() {
  // 루트 요소 반환 위해 임시로 상수에 저장
  const returnValue = this.heap[1];
  // 루트 정점은 가장 마지막 정점으로 대체
  this.heap[1] = this.heap.pop();
  
  // 루트에서부터 가장 마지막으로 내려가기 위한 변수 미리 설정
  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;
      currentIndex = rightIndex;
      // 오른쪽 정점이 왼쪽 정점보다 우선 순위가 높은 경우
    } else {
      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[leftIndex];
      this.heap[leftIndex] = temp;
      currentIndex = leftIndex;
    }
    // 바꾼 정점에서 왼쪽 / 오른쪽 정점의 위치를 다시 구함
    leftIndex = currentIndex * 2;
    rightIndex = currentIndex * 2 + 1;
  }
  
  return returnValue;
}
  
// heap state: [null, 63, 54, 45, 27, 36]
const array = []
array.push(head.pop()); // 63
array.push(head.pop()); // 54
array.push(head.pop()); // 45
array.push(head.pop()); // 36
array.push(head.pop()); // 27
console.log(array);
// [63, 54, 45, 36, 27] - Heap Sort