algorithm 알고리즘 Data Structure 자료구조 Priority Queue 우선순위 큐

[Algorithm] Data Structure - Priority Queue

자료구조 우선순위 큐!

Posted by lim.Chuck on September 14, 2024

Priority Queue?

우선순위 큐(Priority Queue)는 각 요소가 우선순위와 연관된 특별한 형태의 큐입니다. 일반 큐는 먼저 들어온 요소가 먼저 나가지만, 우선순위 큐에서는 우선순위가 높은 요소가 먼저 dequeued(제거)됩니다. 동일한 우선순위를 가진 두 요소가 있을 경우, 삽입 순서(FIFO)에 따라 제거되거나 구현 방식에 따라 다른 규칙이 적용될 수 있습니다.

우선순위 큐의 사용 사례:

  1. 다익스트라 알고리즘(Dijkstra’s Algorithm): 그래프에서 최단 경로를 찾는 데 사용됩니다.
  2. A* 탐색 알고리즘(A* Search Algorithm): 가장 유망한 순서대로 노드를 탐색하기 위해 우선순위 큐를 사용합니다.
  3. 작업 스케줄링(Task Scheduling): 운영체제에서 작업을 우선순위에 따라 스케줄링하는 데 사용됩니다.
  4. 이벤트 시뮬레이션(Event Simulation): 우선순위가 높은 이벤트(예: 긴급 상황)를 먼저 처리합니다.

JavaScript 예제 (Min-Heap 사용):

JavaScript에는 내장된 우선순위 큐가 없지만, 이진 힙을 사용하여 구현할 수 있습니다.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

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

  // 값을 교환하는 헬퍼 메서드
  swap(index1, index2) {
    [this.values[index1], this.values[index2]] = [
      this.values[index2],
      this.values[index1],
    ];
  }

  // 힙 속성을 유지하기 위해 값을 위로 올리는 헬퍼 메서드
  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element.priority >= parent.priority) break;
      this.swap(idx, parentIdx);
      idx = parentIdx;
    }
  }

  // 힙 속성을 유지하기 위해 값을 아래로 내리는 헬퍼 메서드
  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swapIdx = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild.priority < element.priority) {
          swapIdx = leftChildIdx;
        }
      }

      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swapIdx === null && rightChild.priority < element.priority) ||
          (swapIdx !== null && rightChild.priority < leftChild.priority)
        ) {
          swapIdx = rightChildIdx;
        }
      }

      if (swapIdx === null) break;
      this.swap(idx, swapIdx);
      idx = swapIdx;
    }
  }

  enqueue(value, priority) {
    this.values.push({ value, priority });
    this.bubbleUp();
  }

  dequeue() {
    const min = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return min;
  }
}

// 사용 예시
const pq = new PriorityQueue();
pq.enqueue("설거지하기", 2);
pq.enqueue("숙제하기", 1);
pq.enqueue("TV 보기", 3);

console.log(pq.dequeue()); // { value: '숙제하기', priority: 1 }
console.log(pq.dequeue()); // { value: '설거지하기', priority: 2 }

Rust 예제 (BinaryHeap 사용):

Rust는 표준 라이브러리에 BinaryHeap이라는 내장 우선순위 큐를 제공하지만, 기본적으로 최대 힙(max-heap)으로 작동하여 가장 큰 요소가 먼저 제거됩니다. 최소 힙(min-heap)을 만들기 위해서는 역순을 사용할 수 있습니다.

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
32
33
34
35
36
37
38
39
40
41
42

use std::collections::BinaryHeap;
use std::cmp::Reverse;

#[derive(Debug, Eq, PartialEq)]
struct Task {
    priority: i32,
    description: String,
}

// 우선순위를 기준으로 정렬하기 위해 Ord 트레이트 구현
impl Ord for Task {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.priority.cmp(&self.priority)
    }
}

impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut pq = BinaryHeap::new();

    pq.push(Task {
        priority: 2,
        description: String::from("설거지하기"),
    });
    pq.push(Task {
        priority: 1,
        description: String::from("숙제하기"),
    });
    pq.push(Task {
        priority: 3,
        description: String::from("TV 보기"),
    });

    while let Some(task) = pq.pop() {
        println!("{:?}", task);
    }
}

설명:

  • Rust의 BinaryHeap은 기본적으로 최대 힙으로 작동하므로, 우선순위가 높은 작업이 먼저 제거됩니다.
  • Task 구조체를 정의하고 Ord, PartialOrd, Eq, PartialEq 트레이트를 구현하여 작업이 우선순위에 따라 정렬되도록 합니다.

요약:

  • 우선순위 큐는 알고리즘, 스케줄링, 시뮬레이션 등 우선순위가 중요한 상황에서 사용됩니다.
  • JavaScript에서는 이진 힙을 사용하여 우선순위 큐를 구현할 수 있으며, Rust는 효율적인 우선순위 큐 관리를 위해 BinaryHeap을 제공합니다.

Priority Queue?

A priority queue is a special type of queue in which each element is associated with a priority, and elements are dequeued based on their priority rather than just the order they were enqueued. Higher-priority elements are dequeued before lower-priority ones. If two elements have the same priority, they can be dequeued based on their insertion order (FIFO) or other rules depending on the implementation.

Use Cases of Priority Queue:

  1. Dijkstra’s Algorithm: To find the shortest path in a graph.
  2. A* Search Algorithm: A pathfinding algorithm that uses a priority queue to explore nodes in the most promising order.
  3. Task Scheduling: Used in operating systems to schedule tasks based on their priority.
  4. Event Simulation: Events with higher priority (like emergencies) are processed before others.

JavaScript Example (Using a Min-Heap):

JavaScript doesn’t have a built-in priority queue, but it can be implemented using a binary heap.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

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

  // Helper method to swap values
  swap(index1, index2) {
    [this.values[index1], this.values[index2]] = [
      this.values[index2],
      this.values[index1],
    ];
  }

  // Helper method to bubble up the values to maintain the heap property
  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element.priority >= parent.priority) break;
      this.swap(idx, parentIdx);
      idx = parentIdx;
    }
  }

  // Helper method to sink down the values to maintain the heap property
  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swapIdx = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild.priority < element.priority) {
          swapIdx = leftChildIdx;
        }
      }

      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swapIdx === null && rightChild.priority < element.priority) ||
          (swapIdx !== null && rightChild.priority < leftChild.priority)
        ) {
          swapIdx = rightChildIdx;
        }
      }

      if (swapIdx === null) break;
      this.swap(idx, swapIdx);
      idx = swapIdx;
    }
  }

  enqueue(value, priority) {
    this.values.push({ value, priority });
    this.bubbleUp();
  }

  dequeue() {
    const min = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return min;
  }
}

// Usage
const pq = new PriorityQueue();
pq.enqueue("Clean the dishes", 2);
pq.enqueue("Do homework", 1);
pq.enqueue("Watch TV", 3);

console.log(pq.dequeue()); // { value: 'Do homework', priority: 1 }
console.log(pq.dequeue()); // { value: 'Clean the dishes', priority: 2 }

Rust Example (Using BinaryHeap):

Rust provides a built-in priority queue called BinaryHeap in its standard library, but it works as a max-heap by default, meaning the largest element will be dequeued first. We can create a min-heap by using reverse order.

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
32
33
34
35
36
37
38
39
40
41

use std::collections::BinaryHeap;
use std::cmp::Reverse;

#[derive(Debug, Eq, PartialEq)]
struct Task {
    priority: i32,
    description: String,
}

impl Ord for Task {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.priority.cmp(&self.priority)
    }
}

impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut pq = BinaryHeap::new();

    pq.push(Task {
        priority: 2,
        description: String::from("Clean the dishes"),
    });
    pq.push(Task {
        priority: 1,
        description: String::from("Do homework"),
    });
    pq.push(Task {
        priority: 3,
        description: String::from("Watch TV"),
    });

    while let Some(task) = pq.pop() {
        println!("{:?}", task);
    }
}

Explanation:

  • In Rust, BinaryHeap works as a max-heap by default, so tasks with higher priority are dequeued first.
  • We define a custom Task struct and implement the Ord, PartialOrd, Eq, and PartialEq traits so that tasks are ordered by their priority.

Summary:

  • Priority queues are used in algorithms, scheduling, and simulations where prioritization is key.
  • They can be implemented in JavaScript using a binary heap, and Rust offers a BinaryHeap for efficient priority queue management.
FEATURED TAGS
git 알고리즘 algorithm js 기초 js 기초 문법 js 문법 자료구조 Data Structure Graphs React 그래프 러스트 rust 집합 Sets front 수학 정렬 Math Sorting 간단예제 문자열 Strings github AWS 이벤트 버블링 이벤트 캡처링 탐색 LLM MCP Searches 컴파일러 트리 AI Cloud Front Cursor MCP 사용법 bubbling capturing s3 개발자도구 광고 구글 자동색인 깃허브 광고 라이브러리 러스트 설치 리엑트 버킷 비교 사이트맵 아마존 예제 웹 접근성 이미지 업로드 최장 공통 부분수열 캐시 텍스트 프레임워크 AI통합 API Adsense Claude Compiler SQL SWC Speedy Web Compiler Trees js 변수 js 생성자함수 npm nuxt pipeline project management robots rust 구축 rust setting rust setup text utterances
FRIENDS