[자료구조] 힙(Heap)과 우선순위 큐(Priority Queue)

개발지식/자료구조

[자료구조] 힙(Heap)과 우선순위 큐(Priority Queue)

thinktank911 2025. 10. 20. 22:32

이진트리 (Binary Tree)

트리는 데이터들을 계층 구조로 표현한 자료구조로, 그중에서도 가장 기본이 되는 게 이진트리(Binary Tree)이다.

"각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조"이며 하나의 부모는 왼쪽 자식(left), 오른쪽 자식(right)을 가진다.

        (1)
       /   \
     (2)   (3)
    /  \
  (4)  (5)

1: 루트(root) 노드
2, 3: 1의 자식(child) 노드
4, 5: 2의 자식 노드

이진트리는 이렇게 부모-자식 관계를 표현하며, 탐색(Search), 정렬(Sort), 힙(Heap) 등의 핵심 구조의 기초가 된다.

완전이진트리(Complete Binary Tree)

이진트리의 종류 중 하나로 "마지막 레벨을 제외하고는 모든 노드가 꽉 차 있으며, 마지막 레벨의 노드들은 왼쪽부터 순서대로 채워진 트리"를 말한다. 힙(Heap)이 바로 이 완전이진트리 형태를 기반으로 하는 자료구조다.

        (1)
       /   \
     (2)   (3)
    /  \   /
  (4) (5) (6)

✔️ 특징

빈 칸 없이 왼쪽부터 차례대로 채워진다.
배열로 표현하기 쉬움 (인덱스로 부모-자식 관계 표현 가능)

예를 들어 위 트리를 배열로 표현하면:

[1, 2, 3, 4, 5, 6]

부모 인덱스 = (i - 1) / 2
왼쪽 자식 = 2*i + 1
오른쪽 자식 = 2*i + 2

힙(Heap)

완전이진트리를 기반으로 한 자료구조가 바로 힙(Heap)이다.

힙은 부모와 자식 노드 간의 우선순위 관계를 가지는 즉, 부모 노드의 값이 자식 노드보다 항상 크거나 작다는 규칙을 가지는 트리다.

이 규칙에 따라 힙은 두 가지로 나뉜다.

최대 힙(Max Heap)

부모 노드 ≥ 자식 노드
가장 큰 값이 루트에 위치

        (9)
       /   \
     (6)   (7)
    /  \
  (3)  (5)

최소 힙(Min Heap)

부모 노드 ≤ 자식 노드
가장 작은 값이 루트에 위치

        (2)
       /   \
     (3)   (4)
    /  \
  (8)  (9)

힙의 핵심 연산

연산	설명	시간복잡도
삽입 (insert)	새 원소를 넣고 힙 구조를 유지	O(log n)
삭제 (delete)	루트(최댓값/최솟값) 제거 후 재정렬	O(log n)
조회 (peek)	루트 값 확인	O(1)

힙은 항상 완전이진트리 구조를 유지하므로, 배열로 구현하기가 쉽고 빠르다.

Min Heap 기반 구현 예시

class MinHeap {
  constructor() {
    this.heap = [];
  }

  // 현재 힙 크기
  size() {
    return this.heap.length;
  }

  // 루트(최솟값) 조회
  peek() {
    return this.heap[0];
  }

  // 값 삽입
  insert(value) {
    this.heap.push(value);
    this._heapifyUp();
  }

  // 최솟값 제거
  extractMin() {
    if (this.size() === 0) return null;
    if (this.size() === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._heapifyDown();
    return min;
  }

  // 삽입 후 위로 올리기
  _heapifyUp() {
    let index = this.size() - 1;

    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);

      // 부모보다 크면 멈춤
      if (this.heap[index] >= this.heap[parentIndex]) break;

      // 부모와 교체
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }

  // 루트 제거 후 아래로 내리기
  _heapifyDown() {
    let index = 0;
    const length = this.size();

    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let smallest = index;

      // 왼쪽 자식이 더 작다면 갱신
      if (left < length && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }

      // 오른쪽 자식이 더 작다면 갱신
      if (right < length && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }

      // 자식이 더 크면 종료
      if (smallest === index) break;

      // 교체
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

Max Heap 기반 구현 예시

class MaxHeap {
  constructor() {
    this.heap = [];
  }

  // 현재 힙의 크기 반환
  size() {
    return this.heap.length;
  }

  // 힙의 최댓값(루트) 반환
  peek() {
    return this.heap[0];
  }

  // 새로운 값 삽입
  insert(value) {
    this.heap.push(value);             // 1. 배열 끝에 삽입
    this._heapifyUp();                 // 2. 위로 올라가며 정렬
  }

  // 최댓값(루트) 삭제
  extractMax() {
    if (this.size() === 0) return null;
    if (this.size() === 1) return this.heap.pop();

    const max = this.heap[0];
    this.heap[0] = this.heap.pop();    // 마지막 노드를 루트로 이동
    this._heapifyDown();               // 아래로 내려가며 정렬
    return max;
  }

  // 🔼 삽입 후 위로 올리기
  _heapifyUp() {
    let index = this.size() - 1;
    const inserted = this.heap[index];

    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      const parent = this.heap[parentIndex];

      if (parent >= inserted) break;   // 부모가 더 크면 멈춤

      // 부모와 교체
      this.heap[parentIndex] = inserted;
      this.heap[index] = parent;
      index = parentIndex;
    }
  }

  // 🔽 삭제 후 아래로 내리기
  _heapifyDown() {
    let index = 0;
    const length = this.size();
    const root = this.heap[index];

    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let largest = index;

      if (left < length && this.heap[left] > this.heap[largest]) {
        largest = left;
      }

      if (right < length && this.heap[right] > this.heap[largest]) {
        largest = right;
      }

      if (largest === index) break; // 자식보다 크면 멈춤

      [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
      index = largest;
    }
  }
}

우선순위 큐(Priority Queue)

일반 큐(Queue)는 들어온 순서대로 처리하지만, 우선순위 큐는 우선순위가 높은 데이터부터 처리하는 큐이다.

일반 큐	우선순위 큐
FIFO (선입선출)	우선순위 높은 순서대로
순서가 중요	중요도가 중요

이를테면,

환자	증상	우선순위
A	감기	1
B	골절	3
C	심장마비	5

일반 큐 → A → B → C
우선순위 큐 → C → B → A

힙과의 관계

우선순위 큐를 단순히 배열로 구현하면 삽입할 때마다 정렬해야 해서 비효율적이므로 바로 힙을 사용한다.

힙은 항상 최댓값(혹은 최솟값)을 빠르게 꺼낼 수 있으므로, 우선순위 큐를 효율적으로 구현하기 위한 최적의 자료구조다.

Min Heap 기반 우선순위 큐

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  enqueue(value, priority) {
    this.heap.push({ value, priority });
    this.heap.sort((a, b) => a.priority - b.priority);
  }

  dequeue() {
    return this.heap.shift(); // 우선순위 가장 낮은 값(최소 priority) 제거
  }
}

const pq = new PriorityQueue();
pq.enqueue("감기", 3);
pq.enqueue("골절", 2);
pq.enqueue("심장마비", 1);

console.log(pq.dequeue()); // 👉 { value: '심장마비', priority: 1 }

Max Heap 기반 우선순위 큐

// 🔹 최대 힙 클래스
class MaxHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }

  peek() {
    return this.heap[0];
  }

  // 요소 삽입
  insert(value) {
    this.heap.push(value);
    this._heapifyUp();
  }

  // 루트(최댓값) 제거
  extractMax() {
    if (this.size() === 0) return null;
    if (this.size() === 1) return this.heap.pop();

    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._heapifyDown();
    return max;
  }

  _heapifyUp() {
    let index = this.size() - 1;

    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index].priority <= this.heap[parentIndex].priority) break;

      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }

  _heapifyDown() {
    let index = 0;
    const length = this.size();

    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let largest = index;

      if (left < length && this.heap[left].priority > this.heap[largest].priority) {
        largest = left;
      }

      if (right < length && this.heap[right].priority > this.heap[largest].priority) {
        largest = right;
      }

      if (largest === index) break;

      [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
      index = largest;
    }
  }
}

// 🔹 우선순위 큐 클래스 (MaxHeap 사용)
class PriorityQueue {
  constructor() {
    this.heap = new MaxHeap();
  }

  // enqueue: 값과 우선순위를 함께 추가
  enqueue(value, priority) {
    this.heap.insert({ value, priority });
  }

  // dequeue: 우선순위가 가장 높은 요소 꺼내기
  dequeue() {
    const max = this.heap.extractMax();
    return max ? max.value : null;
  }

  // peek: 현재 우선순위가 가장 높은 요소 확인
  peek() {
    const top = this.heap.peek();
    return top ? top.value : null;
  }

  size() {
    return this.heap.size();
  }
}

'개발지식 > 자료구조' 카테고리의 다른 글

[자료구조] 트리(Tree) (0)	2025.11.10
[자료구조] 탐색(검색) 알고리즘 (Search Algorithm) (0)	2025.11.04
[자료구조] 정렬 (Sort) - 병합 정렬, 퀵 정렬 (0)	2025.10.27
[자료구조] 스택(Stack)과 큐(Que) (0)	2025.10.14
[자료구조] 해시(Hash) (1)	2025.09.26

현재글[자료구조] 힙(Heap)과 우선순위 큐(Priority Queue)

홍익인간 개발자

널리 세상을 이롭게 하고 싶은 개발자

Today :
Yesterday :

일	월	화	수	목	금	토
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

홍익인간 개발자