우선순위 큐와 힙: 개념, 특징 with JS(Java Script)

 

 

 

 

우선순위 큐와 힙은 데이터를 관리하고 탐색하기 위한 중요한 도구입니다.

이 글에서는 우선순위 큐와 힙의 개념, 특징, 그리고 자바스크립트를 사용한 구현 방법을 알아보겠습니다.

---

우선순위 큐

우선순위 큐는 데이터가 입력된 순서가 아니라 우선순위에 따라 처리되는 자료구조입니다. 이는 FIFO(First-In-First-Out) 원칙을 따르는 일반적인 큐와 다릅니다.

---

힙

힙은 이진 트리 형태를 가지며 우선순위 큐를 구현하기 위한 자료구조입니다. 힙은 보통 최대 힙과 최소 힙으로 구분되며, 최대 힙은 루트가 가장 큰 값을 가지고 최소 힙은 루트가 가장 작은 값을 가집니다.

---

힙의 특징

• 우선순위가 높은 요소가 먼저 처리됩니다.
• 완전 이진 트리의 형태를 가지며, 요소 추가 및 삭제 시 트리가 재조정됩니다.

---

힙 요소 추가 알고리즘

1. 새로운 요소는 힙의 가장 마지막에 추가됩니다.
2. 새로운 요소가 부모 요소보다 우선순위가 높으면 부모와 위치를 변경합니다.
3. 이러한 과정을 반복하여 가장 우선순위가 높은 요소가 루트가 됩니다.

---

힙 요소 제거 알고리즘

1. 루트 요소를 제거합니다.
2. 가장 마지막 요소를 루트로 이동시킵니다.
3. 새로운 루트와 자식 요소를 비교하여 우선순위가 높은 쪽과 위치를 변경합니다.
4. 이 과정을 반복하여 힙의 균형을 유지합니다.

---

자바스크립트에서의 구현

자바스크립트에서 힙을 구현할 때는 주로 배열을 사용합니다. 각 노드는 배열의 요소로 표현되며, 인덱스를 이용하여 부모와 자식 관계를 나타냅니다.

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

    // 힙 요소 추가
    insert(value) {
        this.heap.push(value);
        this.bubbleUp();
    }

    // 힙 요소 제거
    extractMax() {
        const max = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.sinkDown();
        }
        return max;
    }

    // 추가적인 메소드 구현 등
}