Priority queue là gì?

Hàng đợi ưu tiên (priority queue) là một loại hàng đợi (queue) đặc biệt, trong đó mỗi phần tử (element) được liên kết với một mức độ ưu tiên (priority) và được phục vụ theo mức độ ưu tiên của nó. Nếu các phần tử có cùng mức độ ưu tiên xảy ra, chúng sẽ được phục vụ theo thứ tự của chúng trong hàng đợi.

Nói chung, giá trị của bản thân phần tử được xem xét để chỉ định mức độ ưu tiên. Ví dụ phần tử có giá trị cao nhất được coi là phần tử có mức ưu tiên cao nhất. Tuy nhiên, trong các trường hợp khác, chúng ta có thể giả sử phần tử có giá trị thấp nhất là phần tử có mức độ ưu tiên cao nhất. Chúng ta cũng có thể thiết lập các ưu tiên theo nhu cầu của chúng tôi.

Triển khai (implementation) hàng đợi ưu tiên (priority queue)

Hàng đợi ưu tiên có thể được triển khai bằng cách sử dụng mảng (array), danh sách liên kết (linked list), cấu trúc dữ liệu heap hoặc cây tìm kiếm nhị phâ (binary search tree)n. Trong số các cấu trúc dữ liệu này, cấu trúc dữ liệu heap cung cấp việc triển khai hiệu quả các hàng đợi ưu tiên.

Bên dưới là code triển khai (implementation) hàng đợi ưu tiên (priority queue) bằng heap trong C:

// Priority Queue implementation in C

#include <stdio.h>
int size = 0;
void swap(int *a, int *b) {
  int temp = *b;
  *b = *a;
  *a = temp;
}

// Function to heapify the tree
void heapify(int array[], int size, int i) {
  if (size == 1) {
    printf("Single element in the heap");
  } else {
    // Find the largest among root, left child and right child
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l  array[largest])
      largest = l;
    if (r  array[largest])
      largest = r;

    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      swap(&array[i], &array[largest]);
      heapify(array, size, largest);
    }
  }
}

// Function to insert an element into the tree
void insert(int array[], int newNum) {
  if (size == 0) {
    array[0] = newNum;
    size += 1;
  } else {
    array[size] = newNum;
    size += 1;
    for (int i = size / 2 - 1; i >= 0; i--) {
      heapify(array, size, i);
    }
  }
}

// Function to delete an element from the tree
void deleteRoot(int array[], int num) {
  int i;
  for (i = 0; i = 0; i--) {
    heapify(array, size, i);
  }
}

// Print the array
void printArray(int array[], int size) {
  for (int i = 0; i 

Một số ứng dụng của hàng đợi ưu tiên (priority queue) là:

• Thuật toán Dijkstra
• Để triển khai ngăn xếp (stack)
• Để cân bằng tải (load balancing ) và xử lý ngắt (interrupt) trong hệ điều hành
• Để nén dữ liệu trong mã Huffman