双端优先队列

2024 年 8 月 28 日 | 阅读 9 分钟

双端优先队列简介

双端优先队列 (DEPQ) 是一种数据结构，用于存储元素集合，其中每个元素都关联着一个优先级或值。元素可以根据其优先级从队列的两端插入和移除。

最高优先级的元素可以从队列的两端访问，而无需移除。在 DEPQ 中，元素以保持其优先级顺序的方式存储，因此最高优先级的元素总是位于队列的前端或后端，具体取决于实现方式。

基本术语

优先队列 - **优先队列**是项目的集合，其中每个项目都有一个优先级，并且项目按优先级顺序处理。

双端队列 - **双端队列**是允许从队列的前端和后端插入和删除项目的项目集合。

DEPQ 的属性

DEPQ 允许在队列的两端执行插入和删除带优先级项目的操作。
无论它们在队列中的位置如何，优先级较高的元素总是首先被处理。
因此，DEPQ 是一种对调度、任务管理和资源分配应用程序很有价值的数据结构。
可以使用多种数据结构来构建 DEPQ，包括二叉堆、斐波那契堆和平衡二叉搜索树。
要使用的最佳数据结构取决于特定应用程序的需求以及时间复杂度和空间复杂度之间的权衡。

DEPQ 支持的操作

双端优先队列 (DEPQ) 执行以下操作：

getMin()：此函数返回最小元素。
getMax()：此函数返回最大元素
put(x)：此函数将元素“x”插入 DEPQ。
removeMin()：顾名思义，它从 DEPQ 中移除最小元素
removeMax()：它从 DEPQ 中移除最大元素。

DEPQ 的自平衡 BST 实现

DEPQ 的自平衡 BST 实现为其所有操作提供了有效的时间复杂度，并且其空间复杂度与其他实现相当。自平衡树自动保持其平衡结构，确保在处理大数据集时快速可靠的性能。

在 C++ 中，自平衡二叉搜索树（例如红黑树或 AVL 树）通常用于实现 set 容器。这些数据结构提供了具有有效最坏情况和平均情况时间复杂度的 set 操作。

// C++ program to implement double-ended
// priority queue using self-balancing BST
#include <iostream>
#include <set>

using namespace std;

// Defining DEPQ class
class DEPQ
{
private:
    set<int> s;

public:
    // Insert a value into the DEPQ
    // Time Complexity = O(Log n)
    void put(int val)
    {
        s.insert(val);
    }

    // Get the minimum value in the DEPQ
    // Time Complexity = O(1)
    int getMin()
    {
        return *s.begin();
    }

    // Get the maximum value in the DEPQ
    // Time Complexity = O(1)
    int getMax()
    {
        return *prev(s.end());
    }

    // Delete the minimum value from the DEPQ
    // Time Complexity = O(Log n)
    void removeMin()
    {
        if (!s.empty())
        {
            s.erase(s.begin());
        }
    }

    // Delete the maximum value from the DEPQ
    // Time Complexity = O(Log n)
    void removeMax()
    {
        if (!s.empty())
        {
            s.erase(prev(s.end()));
        }
    }

    // Get the size of the DEPQ
    // Time Complexity = O(1)
    int size()
    {
        return s.size();
    }

    // Check if the DEPQ is empty
    // Time Complexity = O(1)
    bool isEmpty()
    {
        return s.empty();
    }
};

// Driver function
int main()
{
    DEPQ d;

    int choice, val;

    // Printing Options
    cout << "\nDEPQ Operations:" << endl;
    cout << "1. Insert an Element" << endl;
    cout << "2. Get Minimum Element" << endl;
    cout << "3. Get Maximum Element" << endl;
    cout << "4. Delete Minimum Element" << endl;
    cout << "5. Delete Maximum Element" << endl;
    cout << "6. Size" << endl;
    cout << "7. Is Empty?" << endl;
    cout << "0. Exit" << endl;

    do
    {
        cout << "Enter your choice: ";
        cin >> choice;

        // Switched case is used to make this program user driven.
        switch (choice)
        {

        // Case 1 to insert
        case 1:
            cout << "Enter the value to put: ";
            cin >> val;
            d.put(val);
            cout << "Value inserted successfully." << endl;
            break;

        // Case 2 to get minimum element
        case 2:
            if (!d.isEmpty())
            {
                cout << "Minimum value: " << d.getMin() << endl;
            }
            else
            {
                cout << "DEPQ is empty." << endl;
            }
            break;

        // Case 3 to get maximum element
        case 3:
            if (!d.isEmpty())
            {
                cout << "Maximum value: " << d.getMax() << endl;
            }
            else
            {
                cout << "DEPQ is empty." << endl;
            }
            break;

        // Case 4 to remove minimum element
        case 4:
            if (!d.isEmpty())
            {
                d.removeMin();
                cout << "Minimum value deleted successfully." << endl;
            }
            else
            {
                cout << "DEPQ is empty." << endl;
            }
            break;

        // Case 5 to remove maximum element
        case 5:
            if (!d.isEmpty())
            {
                d.removeMax();
                cout << "Maximum value deleted successfully." << endl;
            }
            else
            {
                cout << "DEPQ is empty." << endl;
            }
            break;

        // Case 6 to find the size of the DEPQ
        case 6:
            cout << "DEPQ size: " << d.size() << endl;
            break;

        // Case 1 to check emptiness of DEPQ
        case 7:
            if (d.isEmpty())
            {
                cout << "DEPQ is empty." << endl;
            }
            else
            {
                cout << "DEPQ is not empty." << endl;
            }
            break;

        // Case 0 to exit
        case 0:
            cout << "Successfully Exited!" << endl;
            break;

        // Default
        default:
            cout << "Invalid choice. Please try again." << endl;
        }
    } while (choice != 0);

    return 0;
}

输出

DEPQ Operations:   
1. Insert an Element
2. Get Minimum Element    
3. Get Maximum Element    
4. Delete Minimum Element 
5. Delete Maximum Element 
6. Size
7. Is Empty?       
0. Exit
Enter your choice: 1
Enter the value to put: 25
Value inserted successfully.
Enter your choice: 1
Enter the value to put: 75
Value inserted successfully.
Enter your choice: 1
Enter the value to put: 30
Value inserted successfully.
Enter your choice: 1
Enter the value to put: 90
Value inserted successfully.
Enter your choice: 1
Enter the value to put: 55
Value inserted successfully.
Enter your choice: 6
DEPQ size: 5
Enter your choice: 7
DEPQ is not empty.
Enter your choice: 2
Minimum value: 25
Enter your choice: 3
Maximum value: 90
Enter your choice: 4
Minimum value deleted successfully.
Enter your choice: 5
Maximum value deleted successfully.
Enter your choice: 2
Minimum value: 30
Enter your choice: 3
Maximum value: 75
Enter your choice: 0
Successfully Exited!

每个函数的时间复杂度

put()	O(logn)
removeMin()	O(logn)
removeMax()	O(logn)
getMin()	O(1)
getMax()	O(1)
size()	O(1)
isEmpty()	O(1)

Java 中双端优先队列的实现

在此实现中，我们使用 TreeSet 以排序方式存储元素。TreeSet 允许我们轻松检索最小和最大元素，并以 O(log n) 的时间复杂度执行插入和删除操作。

// Java Program to implement DEPQ using self-balancing BST (TreeSet)
import java.util.TreeSet;

class DblEndedPQ {

    private TreeSet<Integer> treeSet;

    public DblEndedPQ() {
        treeSet = new TreeSet<Integer>();
    }

    // Returns size of the queue.
    // Time Complexity = O(1)
    public int size() {
        return treeSet.size();
    }

    // Returns true if the queue is empty.
    // Time Complexity = O(1)
    public boolean isEmpty() {
        return treeSet.isEmpty();
    }

    // Inserts an element.
    // Time Complexity = O(Log n)
    public void put(int x) {
        treeSet.add(x);
    }

    // Returns minimum element.
    // Time Complexity = O(1)
    public int getMin() {
        return treeSet.first();
    }

    // Returns maximum element.
    // Time Complexity = O(1)
    public int getMax() {
        return treeSet.last();
    }

    // Deletes minimum element.
    // Time Complexity = O(Log n)
    public void removeMin() {
        if (!treeSet.isEmpty()) {
            treeSet.pollFirst();
        }
    }

    // Deletes maximum element.
    // Time Complexity = O(Log n)
    public void removeMax() {
        if (!treeSet.isEmpty()) {
            treeSet.pollLast();
        }
    }
}

public class Main {

    public static void main(String[] args) {
        // Creating a DblEndedPQ Object
        DblEndedPQ depq = new DblEndedPQ();

        // Inserting Elements
        depq.put(25);
        System.out.println("Inserted 25 Successfully!");
        depq.put(75);
        System.out.println("Inserted 75 Successfully!");
        depq.put(30);
        System.out.println("Inserted 30 Successfully!");
        depq.put(90);
        System.out.println("Inserted 90 Successfully!");
        depq.put(55);
        System.out.println("Inserted 55 Successfully!");

        // Performing operations
        System.out.println("Size of the DEPQ : " + depq.size());
        System.out.println("Is empty? : " + depq.isEmpty());
        System.out.println("Minimum Element : " + depq.getMin());
        System.out.println("Maximum Element : " + depq.getMax());

        // Deleting the maximum element
        depq.removeMax();
        System.out.println("Maximum Element Deleted Successfully!");
        System.out.println("New Maximum Element : " + depq.getMax());

        // Deleting the maximum element
        depq.removeMin();
        System.out.println("Minimum Element Deleted Successfully!");
        System.out.println("New Minimum Element : " + depq.getMin());

        System.out.println("Size of the DEPQ now : " + depq.size());
    }
}

输出

Inserted 25 Successfully!
Inserted 75 Successfully!
Inserted 30 Successfully!
Inserted 90 Successfully!
Inserted 55 Successfully!
Size of the DEPQ : 5
Is empty? : false
Minimum Element : 25
Maximum Element : 90
Maximum Element Deleted Successfully!
New Maxmium Element : 75
Minimum Element Deleted Successfully!
New Minimum Element : 30
Size of the DEPQ now : 3

Python 中双端优先队列的实现

此实现中使用 bisect 模块，它支持维护排序列表，而无需在每次插入后对列表进行排序。使用 bisect.insort() 函数，元素插入到正确的位置以保持排序顺序。这使我们能够以 O(log n) 时间复杂度的操作插入和删除项目，并以 O(1) 时间获取最小和最大元素。

import bisect

class DblEndedPQ:

    def __init__(self):
        self.lst = []

    # Returns the size of the queue.
    # Time Complexity = O(1)
    def size(self):
        return len(self.lst)

    # Returns true if the queue is empty.
    # Time Complexity = O(1)
    def isEmpty(self):
        return len(self.lst) == 0

    # Inserts an element.
    # Time Complexity = O(Log n)
    def insert(self, x):
        bisect.insort(self.lst, x)

    # Returns minimum element.
    # Time Complexity = O(1)
    def getMin(self):
        return self.lst[0]

    # Returns maximum element.
    # Time Complexity = O(1)
    def getMax(self):
        return self.lst[-1]

    # Deletes minimum element.
    # Time Complexity = O(Log n)
    def deleteMin(self):
        if not self.isEmpty():
            self.lst.pop(0)

    # Deletes maximum element.
    # Time Complexity = O(Log n)
    def deleteMax(self):
        if not self.isEmpty():
            self.lst.pop()

# Driver code
if __name__ == '__main__':
    # Creating a DblEndedPQ object
    depq = DblEndedPQ()

    # Inserting elements into DEPQ
    depq.insert(25)
    print("Inserted 25 Successfully!")
    depq.insert(75)
    print("Inserted 75 Successfully!")
    depq.insert(30)
    print("Inserted 30 Successfully!")
    depq.insert(90)
    print("Inserted 90 Successfully!")
    depq.insert(55)
    print("Inserted 55 Successfully!")

    # Performing operations
    print(f"Size of the DEPQ : {depq.size()}")
    print(f"is Empty? : {depq.isEmpty()}")
    print(f"Minimum Element : {depq.getMin()}")
    print(f"Maximum Element : {depq.getMax()}")

    # Deleting Maximum element
    depq.deleteMax()
    print("Maximum Elemented Deleted Successfully!")
    print(f"Maximum Element : {depq.getMax()}")

    # Deleting Minimum element
    depq.deleteMin()
    print("Minimum Elemented Deleted Successfully!")
    print(f"New Minimum Element : {depq.getMin()}")
    print(f"Size of the DEPQ now : {depq.size()}")

输出

Inserted 25 Successfully!
Inserted 75 Successfully!
Inserted 30 Successfully!
Inserted 90 Successfully!
Inserted 55 Successfully!
Size of the DEPQ : 5
is Empty? : False
Minimum Element : 25
Maximum Element : 90
Maximum Elemented Deleted Successfully!
Maximum Element : 75
Minimum Elemented Deleted Successfully!
New Minimum Element : 30
Size of the DEPQ now : 3

堆实现与 BBST 实现的 DEPQ 比较

使用堆与平衡二叉搜索树 (BBST) 实现双端优先队列 (DEPQ)

堆实现

堆是满足堆属性的完全二叉树。
插入元素需要 O(log n) 时间，其中 n 是堆中的元素数量。
删除最小或最大元素需要 O(log n) 时间。
获取最小或最大元素需要 O(1) 时间。
堆的空间复杂度为 O(n)。

平衡二叉搜索树 (BBST) 实现

BBST 是满足平衡属性的二叉树，例如 AVL 树或红黑树。
插入元素需要 O(log n) 时间，其中 n 是树中的元素数量。
删除最小或最大元素需要 O(log n) 时间。
获取最小或最大元素需要 O(log n) 时间。
BBST 的空间复杂度为 O(n)。

比较这两种实现，我们可以看到

堆在获取最小或最大元素方面具有更快的时间复杂度（O(1) vs. O(log n)），但在插入和删除元素方面具有较慢的时间复杂度（O(log n) vs. O(log n)）。
BBST 在获取最小或最大元素方面具有较慢的时间复杂度，但在插入和删除元素方面具有更快的时间复杂度。
两种实现的空间复杂度相同。
因此，实现选择取决于具体的用例和最常执行的操作。如果获取最小或最大元素是更频繁的操作，则堆可能是更好的选择。另一方面，如果插入和删除元素更频繁，则 BBST 可能是更好的选择。

下一个主题B+ 树删除

双端优先队列