一、priority_queueu的使用

1.priority_queue的介紹

優先佇列是一種容器配接器，默認情況下STL（頭檔案是<queue>）中使用vector作為其底層的資料結構，也就是本質上priority_queue就是vector，然后再vector的基礎上添加一些演算法并將其封裝成介面對外暴露，而其中的演算法是調整堆的演算法，所以在C++中priority_queue就是堆，而且默認情況下是大根堆，

2.priority_queue的定義

①定義大根堆

priority_queue<int> heap; // 默認就是大根堆
priority_quueue<int, vector<int>, less<int>> heap;

②定義小根堆

priority_queue<int, vector<int>, greater<int>> heap;

3.priority_queue的常用介面

測驗代碼：

#include <queue>

using namespace std;

int main()
{
    priority_queue<int> heap;
    heap.push(1);
    heap.push(2);
    heap.push(3);
    heap.push(4);
    while (!heap.empty()) {
        cout << heap.top() << ' '; // 將堆中的所有元素彈出
        heap.pop();
    }
    return 0;
}

二、priority_queue的模擬實作

既然priority_queue是堆，所以我們要模擬實作priority_queue就一定了解調整堆的演算法，而其中最最重要的兩個演算法就是：將元素插入堆時使用的向上調整法shiftUp()和洗掉堆頂元素的向下調整演算法shiftDown()，

調整堆演算法-shiftUp()-shiftDown()

shiftUp()演算法

圖示

代碼實作：

// 大根堆的向上調整演算法
void shiftUp(vector<int>& arr, int child) {
    while (child > 0) {
        int parent = (child - 1) / 2;
        if (arr[parent] < arr[child]) {
            swap(arr[parent], arr[child]);
        } else {
            break;
        }
        child = parent;
    }
}

shiftDown()演算法

圖示：

代碼實作：

// 大根堆的向下調整演算法
void shiftDown(vector<int>& arr, int parent) {
    while (parent * 2 + 1 < arr.size()) {
        int child = parent * 2 + 1;
        if (child + 1 < arr.size() && arr[child] < arr[child + 1])
            child ++;
        if (arr[child] > arr[parent]) {
            swap(arr[child], arr[parent]);
            parent = child;
        } else {
            break;
        }
    }
}

仿函式

在使用priority_queue的時候，模板的第一個引數是容器中元素的型別，第二個引數是容器配接器底層封裝的資料結構，第三個引數是仿函式，

**仿函式就是行為類似于函式的物件，所謂函式行為就是“可以使用小括號傳遞引數，并呼叫物件中多載的operator()成員函式，**所以說仿函式的本質就是一個物件，并且物件中的operator()被特殊地處理過了，我們可以在operator（）中寫原本我們想要在函式內部實作的內容，

那為什么要寫一個類并多載它的operator()，而不是直接寫一個函式去呼叫呢？

在一般情況下，我們如果直接呼叫函式，肯定是撰寫一個函式比較方便，因為如果想要使用仿函式一定需要寫一個類，然后定義一個物件才可以使用，

舉個例子：

struct Add { // 不方便
    int operator() (int a, int b) {
        return a + b;  
    }
};

int add(int a, int b) { // 方便
    return a + b;
}

int main() {
    Add add1;
    cout << add1(1, 2) << endl; // 呼叫仿函式
    cout << add(1, 2) << endl; // 呼叫函式
    return 0;
}

但是如果我們想要傳遞一個函式到另一個函式中，這是我們不得不使用函式指標，然后利用函式指標在另一個函式中呼叫這個函式，但是不得不說函式指標不好記，而且不好用，這時就體現出了仿函式的優點：我們如果想要使用相同的功能，只需要傳遞一個物件，然后在另一個函式中只需要物件名(引數)就可以呼叫仿函式了，這樣就方便了不少，

舉個例子：

struct Add {
    int operator() (int a, int b) {
        return a + b;  
    }
};

int addFunc(int a, int b) {
    return a + b;
}

// 在func函式中呼叫仿函式實作a + b
int func(int a, int b, Add& add) {
    return add(a, b);
}
// 在func函式中使用函式指標呼叫addFunc實作a + b
int func(int a, int b, int(*add)(int, int)) {
    return add(a, b);
}

int main() {
    Add add;
    cout << func(1, 2, add); // 傳遞類物件呼叫仿函式函式
    
    cout << func(1, 2, addFunc); // 傳遞函式呼叫函式
    return 0;
}

模擬實作

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

namespace zhy
{
    // less和greater仿函式
    template<class T>
    struct less {
        bool operator() (const T& left, const T& right) {
            return left < right;
        }
    };

    template<class T>
    struct greater {
        bool operator() (const T& left, const T& right) {
            return left > right;
        }
    };

    template<class T, class Container = vector<T>, class Compare = less<T>>
    class priority_queue {
    public:
        priority_queue() {}
		// 利用迭代器范圍初始化建堆
        template<class InputIterator>
        priority_queue(InputIterator first, InputIterator last) {
            while (first != last) {
                container.push_back(*first);
                first ++;
            }
            buildHeap(container);
        }
		// 判空
        bool empty() const {
            return container.empty();
        }
		// 堆中元素個數
        int size() const {
            return container.size();
        }
		// 堆頂元素
        const T& top() const {
            return container.front();
        }
		// 向堆中插入元素
        void push(const T& val) {
            // 向上調整法
            container.push_back(val);
            shiftUp(container, size() - 1);
        }
		// 彈出堆頂元素
        void pop() {
            // 向下調整法
            swap(container[0], container.back());
            container.pop_back();
            shiftDown(container, 0);
        }

    private:
        Container container;
        Compare compare;

    private:
        // 插入元素使用向上調整法
        void shiftUp(Container& con, int child) {
            while (child > 0)
            {
                int parent = (child - 1) >> 1;
                // 使用仿函式比較
                if (compare(con[parent], con[child])) {
                    swap(con[parent], con[child]);
                } else {
                    break;
                }
                child = parent;
            }
        }
		// 洗掉元素使用向下調整法
        void shiftDown(Container& con, int parent) {
            
            while (parent * 2 + 1 < size()) {
                int child = parent * 2 + 1;
                // 使用仿函式比較
                if (child + 1 < size() && compare(con[child], con[child + 1]))
                    child ++;
                // 使用仿函式比較
                if (compare(con[parent], con[child])) {
                    swap(con[child], con[parent]);
                    parent = child;                    
                } else {
                    break;
                }
            }
        }
		// 建堆
        void buildHeap(Container& con) {
            int pos = (size() - 2) / 2;
            while (pos >= 0) {
                shiftDown(con, pos);
                pos --;
            } 
        }

    };
} // namespace zhy