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; }
|
效果