二叉树——优先队列的c++实现_二叉树用优先队列c++

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

优先队列（堆）满足先进先出，而且每次出队的都是队列中最小的（也可以是最大的，看实现过程）。堆是一棵完全二叉树，所以优先队列一般用二叉堆实现。C++有自带的PriorityQueue，但是C#没有。所以写一下

---

一、定义

示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。
1.一棵完全二叉树，所以可以用一个数组表示而不需要用指针。但是用数组就要事先估计堆的大小，所以用一个Capacity表示最大值；

2.因为保持堆序性质，最小元就是在根上，删除后还得做一些调整来保持完全二叉树的结构（实际就是删除最后一个元素，然后把它插入到队列中）;

3.若当前节点下标为i，则i2和i2+1就是它的左右孩子，我们在data[0]处放了一个MIN_INT;

4.入队：首先size++，如果data[size]插入不破坏结构，结束。否则，不断用父亲的值赋给当前节点，直到合适的位置。时间复杂度O(logN)

5.出队：首先根节点置空，记录size点（last）的值然后size–，last能放入当前空穴就结束，否则，不断用儿子中最小的值赋给当前节点。时间复杂度O(logN)

6.队首：直接返回根节点的值，为最小值，O(1)。

---

二、代码实现

头文件：PriorityQueue.h

template<class T>
class PriorityQueue
{
private:
    int Capacity = 100;    		//队列容量
    int size;                 	//队列大小
    T* data;             		//队列变量
    
public:
    PriorityQueue();
    ~PriorityQueue();
    int Size();
    bool Full();   				//判满
    bool Empty(); 				//判空
    void Push(T key); 			//入队
    void Pop();					//出队
    void Clear(); 				//清空
    T Top();					//队首
};

template<class T>
PriorityQueue<T>::PriorityQueue()
{
    data = (T*) malloc((Capacity + 1)*sizeof(T));
    if (!data)
    {
        perror("Allocate dynamic memory");
        return;
    }
    size = 0;
}

template<class T>
PriorityQueue<T>::~PriorityQueue()
{
    while (!Empty())
        Pop();
}

//判空
template<class T>
bool PriorityQueue<T>::Empty()
{
    if (size > 0)
        return false;
    return true;
}

//清空
template<class T>
void PriorityQueue<T>::Clear()
{
    while (!Empty())
        Pop();
}

//判满
template<class T>
bool PriorityQueue<T>::Full()
{
    if (size == Capacity)
        return true;
    return false;
}

//大小
template<class T>
int PriorityQueue<T>::Size()
{
    return size;
}

//入队
template<class T>
void PriorityQueue<T>::Push(T key)
{
    // 空则直接入队  不能省略
    if (Empty())
    {
        data[++size] = key;
        return;
    }

    int i;

    if (Full())
    {
        perror("Priority queue is full\n");
        return;
    }

    for (i = ++size; data[i / 2] > key; i /= 2)
        data[i] = data[i / 2];
    data[i] = key;
}

//出队
template<class T>
void PriorityQueue<T>::Pop()
{
    int i, child;
    T min, last;
    if (Empty())
    {
        perror("Empty queue\n");
        return;
    }

    min = data[1];
    last = data[size--];
    for (i = 1; i * 2 <= size; i = child)
    {
        child = i * 2;
        if (child != size && data[child + 1] < data[child])
            child++;

        if (last > data[child])
            data[i] = data[child];
        else
            break;
    }
    data[i] = last;
}

//队首
template<class T>
T PriorityQueue<T>::Top()
{
    if (Empty())
    {
        perror("Priority queue is full\n");
        return data[0];
    }
    return data[1];
}
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

源文件：

银行有1个服务员，n名顾客，每位顾客有到达时间和服务时间。
先到的顾客先服务，求总服务时间。
输入n 和 n 行 输出服务时间

样例输入：
3
1 3
3 5
10 4
样例输出：14

PriorityQueue.cpp

#include"PriorityQueue.h"
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1000;

//事件 
struct Event
{
    int arrive;        //到达时间
    int service;       //服务时间

    Event(){}
    Event(int a, int s)
    {
        arrive = a;
        service = s;
    }
}cus[MAXN];

int operator > (const Event& a, const Event& b) {
    return a.arrive > b.arrive;
}

int operator < (const Event& a, const Event& b) {
    return a.arrive < b.arrive;
}

int main()
{
    Event minCustomer(INT_MIN,0);
    PriorityQueue<Event> request;      //顾客

    int n, time;
    while (cin >> n)
    {
        for (int i = 0; i < n; i++)
        {
            cin >> cus[i].arrive >> cus[i].service;
            request.Push(cus[i]);   //顾客入队
        }
        time = 0;     //服务时间
        while (!request.Empty())
        {
            Event current = request.Top();
            request.Pop();
            time = max(current.arrive + current.service, time + current.service);
        } 

        cout << time << endl;
    }
    return 0;
}
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