CS106B Assignment6

Foreword

记录2022 winter的CS106B Assignment6

Beyond the Bounds of Arrays

练习一下怎么用debugger看指针指向的数组

Priority Queues and Binary Heaps

用二叉堆实现一个优先队列

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
#include "HeapPQueue.h"
using namespace std;

HeapPQueue::HeapPQueue() {
elems = new DataPoint[INITIAL_SIZE];
logicalSize = 0;
allocatedSize = INITIAL_SIZE;
}

HeapPQueue::~HeapPQueue() {
delete[] elems;
}

int HeapPQueue::size() const {
return logicalSize;
}

bool HeapPQueue::isEmpty() const {
return logicalSize == 0;
}

void HeapPQueue::enqueue(const DataPoint& data) {
if (logicalSize + 1 >= allocatedSize) {
allocatedSize *= 2;
DataPoint* tmp = new DataPoint[allocatedSize];
for (int i = 1; i <= logicalSize; ++i) {
tmp[i] = elems[i];
}
delete[] elems;
elems = tmp;
}
elems[++logicalSize] = data;
int cur = logicalSize;
while (cur > 1 && elems[cur].weight < elems[cur / 2].weight) {
std::swap(elems[cur], elems[cur / 2]);
cur /= 2;
}
}

DataPoint HeapPQueue::peek() const {
if (isEmpty()) {
error("The HeapPQueue is empty.");
}
return elems[1];
}

DataPoint HeapPQueue::dequeue() {
if (isEmpty()) {
error("The HeapPQueue is empty.");
}
DataPoint res = elems[1];
std::swap(elems[1], elems[logicalSize--]);
int cur = 1;
int lson = cur * 2, rson = cur * 2 + 1;
while (true) {
if (lson <= logicalSize && rson <= logicalSize) {
if (elems[lson].weight < elems[rson].weight) {
if (elems[lson].weight < elems[cur].weight) {
std::swap(elems[lson], elems[cur]);
cur = lson;
lson = cur * 2, rson = cur * 2 + 1;
} else {
break;
}
} else {
if (elems[rson].weight < elems[cur].weight) {
std::swap(elems[rson], elems[cur]);
cur = rson;
lson = cur * 2, rson = cur * 2 + 1;
} else {
break;
}
}
} else if (lson <= logicalSize) {
if (elems[lson].weight < elems[cur].weight) {
std::swap(elems[lson], elems[cur]);
cur = lson;
lson = cur * 2, rson = cur * 2 + 1;
} else {
break;
}
} else if (rson <= logicalSize) {
if (elems[rson].weight < elems[cur].weight) {
std::swap(elems[rson], elems[cur]);
cur = rson;
lson = cur * 2, rson = cur * 2 + 1;
} else {
break;
}
} else {
break;
}
}
return res;
}

Apportionment

利用自己实现的HeapPQueue实现美国分配给每个州不同议会席位的算法

利用负数转换小根堆与大根堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Map<string, int> apportion(const Map<string, int>& populations, int numSeats) {
if (populations.size() > numSeats) {
error("There are less seats than states.");
}
Map<string, int> res;
HeapPQueue hpq;
for (auto state : populations) {
res[state] = 1;
hpq.enqueue({state, (-populations[state] / sqrt(2.0))});
--numSeats;
}
while (numSeats--) {
auto u = hpq.dequeue();
res[u.name] += 1;
hpq.enqueue({u.name, (-populations[u.name] / sqrt(res[u.name] * (res[u.name] + 1)))});
}
return res;
}

效果

HeapPQueue

议会席位