Chuyển tới nội dung chính

std::priority_queue

#include <queue>

template <class T, class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type> >
class priority_queue;

std::priority_queue trong C++ là một container adaptor cung cấp giao diện của một hàng đợi ưu tiên (priority queue). Hàng đợi ưu tiên là một cấu trúc dữ liệu mà trong đó mỗi phần tử có một độ ưu tiên nhất định. Phần tử có độ ưu tiên cao nhất luôn được lấy ra đầu tiên (khác với std::queue lấy phần tử được thêm vào đầu tiên).

Tham số​

T​

  • Kiểu dữ liệu của các phần tử trong priority_queue.

Container​

  • Container underlying được sử dụng để lưu trữ các phần tử. Mặc định là std::vector<T>. Bạn cũng có thể sử dụng std::deque<T>.

Compare​

  • Hàm so sánh (comparison function object) để xác định thứ tự ưu tiên của các phần tử. Mặc định là std::less<T>, tức là phần tử lớn nhất sẽ có độ ưu tiên cao nhất (max-heap).

priority_queue​

  • Tên của std::priority_queue bạn muốn tạo.

Đặc điểm​

  1. Thứ tự ưu tiên: Các phần tử trong std::priority_queue được sắp xếp theo thứ tự ưu tiên, không phải theo thứ tự chèn.
  2. Mặc định là max-heap: Theo mặc định, std::priority_queue là một max-heap, nghĩa là phần tử có giá trị lớn nhất sẽ có độ ưu tiên cao nhất. Bạn có thể thay đổi thứ tự ưu tiên bằng cách cung cấp hàm so sánh tùy chỉnh (tham số Compare).
  3. Container Adaptor: Giống như std::stack và std::queue, std::priority_queue là một container adaptor, sử dụng một underlying container (mặc định là std::vector) để lưu trữ các phần tử.
  4. Hạn chế truy cập: Bạn chỉ có thể truy cập phần tử có độ ưu tiên cao nhất (thông qua top()). Không thể truy cập ngẫu nhiên các phần tử bên trong.
  5. Không có iterator: std::priority_queue không cung cấp iterator để duyệt qua các phần tử.
  6. Các thao tác chính: push() (thêm phần tử), pop() (xóa phần tử có độ ưu tiên cao nhất), top() (truy cập phần tử có độ ưu tiên cao nhất), empty() (kiểm tra rỗng), size() (lấy kích thước).
  7. Ưu điểm:
    • Thực hiện cấu trúc dữ liệu hàng đợi ưu tiên một cách dễ dàng.
    • Thao tác push(), pop(), top() có độ phức tạp tốt (thường là O(log n) cho push() và pop(), O(1) cho top()).
  8. Nhược điểm:
    • Hạn chế quyền truy cập, chỉ thao tác được với phần tử có độ ưu tiên cao nhất.
    • Không hỗ trợ duyệt qua các phần tử.
  9. Khi nào nên sử dụng std::priority_queue:
    • Khi bạn cần một cấu trúc dữ liệu cho phép lấy ra phần tử có độ ưu tiên cao nhất một cách nhanh chóng.
    • Khi bạn cần giải quyết các bài toán như:
      • Lập lịch công việc.
      • Tìm đường đi ngắn nhất (ví dụ: thuật toán Dijkstra).
      • Mô phỏng các sự kiện theo thứ tự ưu tiên.
      • Hợp nhất k danh sách đã sắp xếp.

Ví dụ:​

#include <iostream>
#include <queue>
#include <functional> // std::greater
#include <vector>

int main() {
  // 1. Khởi tạo priority_queue rỗng (mặc định là max-heap)
  std::priority_queue<int> pq1;

  // 2. Thêm phần tử vào priority_queue
  pq1.push(30);
  pq1.push(10);
  pq1.push(50);
  pq1.push(20);

  // 3. Lấy phần tử có độ ưu tiên cao nhất (không xóa)
  std::cout << "pq1.top(): " << pq1.top() << '\n'; // Output: pq1.top(): 50

  // 4. Xóa phần tử có độ ưu tiên cao nhất
  pq1.pop();

  // 5. Khởi tạo priority_queue (min-heap)
  std::priority_queue<int, std::vector<int>, std::greater<int>> pq2;

  pq2.push(30);
  pq2.push(10);
  pq2.push(50);
  pq2.push(20);

  std::cout << "pq2.top(): " << pq2.top() << '\n'; // Output: pq2.top(): 10

  // 6. Kiểm tra priority_queue rỗng
  if (pq1.empty()) {
    std::cout << "pq1 is empty\n";
  } else {
    std::cout << "pq1 is not empty\n"; // Output: pq1 is not empty
  }

  // 7. Lấy kích thước priority_queue
  std::cout << "pq1.size(): " << pq1.size() << '\n'; // Output: pq1.size(): 3

  // 8. Sử dụng emplace (C++11)
  std::priority_queue<std::pair<int, int>> pq3;
  pq3.emplace(1, 2);
  pq3.emplace(3, 4);
  std::cout << "pq3.top().second: " << pq3.top().second << '\n'; // Output: pq3.top().second: 4

  // 9. Hoán đổi nội dung 2 priority_queue (C++11)
  std::priority_queue<int> pq4;
  pq4.push(1);
  pq4.push(2);
  std::priority_queue<int> pq5;
  pq5.push(3);
  pq5.push(4);
  pq4.swap(pq5);
    
  std::cout << "pq4: ";
  while (!pq4.empty()) {
      std::cout << pq4.top() << " ";
      pq4.pop();
  }
  std::cout << '\n'; // Output: pq4: 4 3

  std::cout << "pq5: ";
  while (!pq5.empty()) {
      std::cout << pq5.top() << " ";
      pq5.pop();
  }
  std::cout << '\n'; // Output: pq5: 2 1

  return 0;
}

Các cách phổ biến khai báo và khởi tạo một std::priority_queue​

lưu ý
  • std::priority_queue không hỗ trợ khởi tạo từ initializer_list.
  • Khi khởi tạo std::priority_queue từ một container khác, các phần tử sẽ được sao chép (hoặc di chuyển) vào underlying container của std::priority_queue và sau đó được sắp xếp lại theo thứ tự ưu tiên.
  • Mặc định std::priority_queue là max-heap (phần tử lớn nhất ở đầu). Để tạo min-heap (phần tử nhỏ nhất ở đầu), bạn cần sử dụng std::greater<T> làm hàm so sánh.

  1. Khai báo một std::priority_queue rỗng (sử dụng container mặc định std::vector và so sánh mặc định std::less - max heap):​

    #include <queue>

    std::priority_queue<int> pq1; // priority_queue rỗng, kiểu int, sử dụng std::vector làm container underlying, max-heap

  2. Khai báo một std::priority_queue rỗng với container underlying và hàm so sánh cụ thể:​

    #include <queue>
    #include <vector>
    #include <functional> // std::greater

    std::priority_queue<int, std::vector<int>, std::greater<int>> pq2; // priority_queue rỗng, kiểu int, sử dụng std::vector, min-heap

  3. Khởi tạo std::priority_queue từ một range (copy):​

    #include <queue>
    #include <vector>
    #include <iostream>

    int main() {
      std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};

      std::priority_queue<int> pq3(vec.begin(), vec.end()); // Khởi tạo từ một range (copy)

      std::cout << "pq3: ";
      while (!pq3.empty()) {
        std::cout << pq3.top() << " "; // Output: 9 6 5 4 3 2 1 1
        pq3.pop();
      }
      std::cout << '\n';
      
      return 0;
    }

  4. Khởi tạo std::priority_queue từ một container khác và chỉ định hàm so sánh (copy):​

    Tương tự như copy, bạn không thể trực tiếp move, bạn cần thông qua container underlying 
    #include <queue>
    #include <vector>
    #include <functional>
    #include <iostream>

    int main() {
        std::vector<int> vec = { 3, 1, 4, 1, 5, 9, 2, 6 };

        std::priority_queue<int, std::vector<int>, std::greater<int>> pq4(vec.begin(), vec.end()); // Khởi tạo từ một range (copy), min-heap

        std::cout << "pq4: ";
        while (!pq4.empty()) {
            std::cout << pq4.top() << " "; // Output: 1 1 2 3 4 5 6 9
            pq4.pop();
        }
        std::cout << '\n';

        std::deque<int> deq = { 3, 1, 4, 1, 5, 9, 2, 6 };
        std::priority_queue<int, std::deque<int>, std::greater<int>> pq5(deq.begin(), deq.end()); // Khởi tạo từ một range (copy), min-heap
        std::cout << "pq5: ";
        while (!pq5.empty()) {
            std::cout << pq5.top() << " "; // Output: 1 1 2 3 4 5 6 9
            pq5.pop();
        }
        std::cout << '\n';

        return 0;
    }

  5. Di chuyển các phần tử từ một container khác vào priority_queue:​

    #include <iostream>
    #include <queue>
    #include <vector>
    #include <algorithm>

    int main() {
        std::vector<int> vec = { 3, 1, 4, 1, 5, 9, 2, 6 };

        // Tạo một priority_queue tạm thời để sắp xếp các phần tử
        std::priority_queue<int> temp_pq(vec.begin(), vec.end());

        // Di chuyển các phần tử từ priority_queue tạm thời sang priority_queue mới
        std::priority_queue<int> pq6;
        while (!temp_pq.empty()) {
            pq6.push(std::move(temp_pq.top())); // Di chuyển phần tử từ đỉnh
            temp_pq.pop();
        }

        std::cout << "pq6: ";
        while (!pq6.empty()) {
            std::cout << pq6.top() << " "; // Output: 9 6 5 4 3 2 1 1
            pq6.pop();
        }
        std::cout << '\n';

        return 0;
    }

Các kiểu dữ liệu của std::priority_queue​

lưu ý

std::priority_queue là một container adaptor, nó không trực tiếp lưu trữ dữ liệu mà dựa vào underlying container. Do đó, std::priority_queue có thể chứa bất kỳ kiểu dữ liệu nào mà underlying container hỗ trợ, miễn là kiểu dữ liệu đó thỏa mãn các yêu cầu sau:

  • CopyAssignable (có thể gán bằng sao chép): push() có thể sử dụng đến.
  • MoveAssignable (có thể gán bằng di chuyển, từ C++11): push() và emplace() có thể sử dụng đến.
  • Destructible (có thể hủy): Cần thiết để giải phóng bộ nhớ khi các phần tử bị xóa khỏi priority_queue.
  • LessThanComparable (có thể so sánh nhỏ hơn): Nếu sử dụng hàm so sánh mặc định std::less.
  • Hoặc cung cấp hàm so sánh tùy chỉnh (Compare): Để xác định thứ tự ưu tiên.
  1. Các kiểu dữ liệu cơ bản:
    int, float, double, char, bool, long, short,...
  2. Con trỏ:
    int*, char*, MyClass*,...
  3. Các kiểu dữ liệu chuẩn:
    std::string, std::vector, std::list, std::map, std::set, std::pair, std::tuple,...
  4. Các kiểu dữ liệu do người dùng định nghĩa (Classes và Structs):
    Với điều kiện các kiểu dữ liệu này phải thỏa mãn các yêu cầu về CopyAssignable/MoveAssignable, Destructible và cung cấp cách thức so sánh (toán tử < hoặc hàm so sánh tùy chỉnh).
  5. Smart pointers:
    std::unique_ptr, std::shared_ptr

Ví dụ:​

#include <queue>
#include <vector>
#include <iostream>
#include <functional>

int main() {
  std::priority_queue<int> pq1; // Sử dụng std::vector<int> và std::less<int>
  std::priority_queue<double, std::deque<double>, std::greater<double>> pq2; // Sử dụng std::deque<double> và std::greater<double>

  // Lấy các kiểu dữ liệu đặc biệt
  std::priority_queue<int>::value_type val1 = 10; // int
  std::priority_queue<int>::container_type cont1; // std::vector<int>
  std::priority_queue<int>::size_type size1 = pq1.size(); // std::size_t
  std::priority_queue<int>::compare_type comp1 = pq1.key_comp(); // std::less<int>
  std::priority_queue<int>::reference ref1 = pq1.top();
  std::priority_queue<int>::const_reference cref1 = pq1.top();

  std::priority_queue<double, std::deque<double>, std::greater<double>>::value_type val2 = 3.14; // double
  std::priority_queue<double, std::deque<double>, std::greater<double>>::container_type cont2; // std::deque<double>
  std::priority_queue<double, std::deque<double>, std::greater<double>>::size_type size2 = pq2.size(); // std::size_t
  std::priority_queue<double, std::deque<double>, std::greater<double>>::compare_type comp2 = pq2.key_comp(); // std::greater<double>
  std::priority_queue<double, std::deque<double>, std::greater<double>>::reference ref2 = pq2.top();
  std::priority_queue<double, std::deque<double>, std::greater<double>>::const_reference cref2 = pq2.top();

  // In ra các kiểu dữ liệu (có thể khác nhau tùy trình biên dịch)
  std::cout << typeid(val1).name() << std::endl;
  std::cout << typeid(cont1).name() << std::endl;
  std::cout << typeid(size1).name() << std::endl;
  std::cout << typeid(comp1).name() << std::endl;

  std::cout << typeid(val2).name() << std::endl;
  std::cout << typeid(cont2).name() << std::endl;
  std::cout << typeid(size2).name() << std::endl;
  std::cout << typeid(comp2).name() << std::endl;
  
  std::cout << typeid(ref1).name() << std::endl;
  std::cout << typeid(cref1).name() << std::endl;
  std::cout << typeid(ref2).name() << std::endl;
  std::cout << typeid(cref2).name() << std::endl;

  return 0;
}

Các hàm thành viên​

emptyKiểm tra xem std::priority_queue có rỗng hay không
sizeTrả về số lượng phần tử hiện có trong std::priority_queue
topTrả về tham chiếu đến phần tử có độ ưu tiên cao nhất trong std::priority_queue
pushThêm một phần tử mới vào std::priority_queue
emplaceXây dựng (construct) một phần tử mới trực tiếp tại vị trí thích hợp trong std::priority_queue (dựa trên độ ưu tiên)
popXóa phần tử có độ ưu tiên cao nhất (phần tử ở đỉnh) của std::priority_queue
swapHoán đổi nội dung của hai std::priority_queue với nhau
Cập nhật lần cuối vào bởi yutijang

 2025 © cppDocs. Built with Docusaurus.