diff options
Diffstat (limited to '02-data_structures')
3 files changed, 70 insertions, 31 deletions
diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/build_heap.cpp b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/build_heap.cpp index 3cb2e91..020628d 100644 --- a/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/build_heap.cpp +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/build_heap.cpp @@ -31,20 +31,24 @@ class HeapBuilder { void GenerateSwaps() { swaps_.clear(); - // The following naive implementation just sorts - // the given sequence using selection sort algorithm - // and saves the resulting sequence of swaps. - // This turns the given array into a heap, - // but in the worst case gives a quadratic number of swaps. - // - // TODO: replace by a more efficient implementation - for (int i = 0; i < data_.size(); ++i) - for (int j = i + 1; j < data_.size(); ++j) { - if (data_[i] > data_[j]) { - swap(data_[i], data_[j]); - swaps_.push_back(make_pair(i, j)); + + int s = data_.size(); + for (int i = (data_.size() - 2) / 2; i >= 0; i--) { + for (int j = i, k = i; ; j = k) { + int c = (j + 1) * 2 - 1; + if (c < s && data_[k] > data_[c]) + k = c; + c += 1; + if (c < s && data_[k] > data_[c]) + k = c; + + if (k == j) + break; + + swap(data_[j], data_[k]); + swaps_.push_back(make_pair(j, k)); } - } + } } public: diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/job_queue.cpp b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/job_queue.cpp index 920e7ac..a601665 100644 --- a/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/job_queue.cpp +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/job_queue.cpp @@ -3,6 +3,7 @@ #include <algorithm> using std::vector; +using std::swap; using std::cin; using std::cout; @@ -29,20 +30,41 @@ class JobQueue { } void AssignJobs() { - // TODO: replace this code with a faster algorithm. assigned_workers_.resize(jobs_.size()); start_times_.resize(jobs_.size()); vector<long long> next_free_time(num_workers_, 0); + vector<int> workers_queue(num_workers_); + for (int i = 0; i < num_workers_; ++i) + workers_queue[i] = i; for (int i = 0; i < jobs_.size(); ++i) { int duration = jobs_[i]; - int next_worker = 0; - for (int j = 0; j < num_workers_; ++j) { - if (next_free_time[j] < next_free_time[next_worker]) - next_worker = j; - } + int next_worker = workers_queue[0]; assigned_workers_[i] = next_worker; start_times_[i] = next_free_time[next_worker]; next_free_time[next_worker] += duration; + + for (int j = 0, k = 0, w = next_worker; ; j = k, w = next_worker) { + int c = (j + 1) * 2 - 1; + if (c < num_workers_) { + int nw = workers_queue[c]; + if (next_free_time[nw] < next_free_time[w] || (next_free_time[nw] == next_free_time[w] && nw < w)) { + k = c; + w = nw; + } + } + + c += 1; + if (c < num_workers_) { + int nw = workers_queue[c]; + if (next_free_time[nw] < next_free_time[w] || (next_free_time[nw] == next_free_time[w] && nw < w)) + k = c; + } + + if (k == j) + break; + + swap(workers_queue[j], workers_queue[k]); + } } } diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/merging_tables.cpp b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/merging_tables.cpp index 1bcf468..5cbb308 100644 --- a/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/merging_tables.cpp +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/merging_tables.cpp @@ -27,19 +27,32 @@ struct DisjointSets { sets[i].parent = i; } - int getParent(int table) { - // find parent and compress path - } + int getParent(int table) { + if (sets[table].parent == table) + return table; + sets[table].parent = getParent(sets[table].parent); + return sets[table].parent; + } - void merge(int destination, int source) { - int realDestination = getParent(destination); - int realSource = getParent(source); - if (realDestination != realSource) { - // merge two components - // use union by rank heuristic - // update max_table_size - } - } + void merge(int destination, int source) { + int realDestination = getParent(destination); + int realSource = getParent(source); + if (realDestination != realSource) { + if (sets[realDestination].rank >= sets[realSource].rank) { + sets[realDestination].size += sets[realSource].size; + sets[realSource].size = 0; + sets[realSource].parent = realDestination; + if (sets[realDestination].rank == sets[realSource].rank) + sets[realDestination].rank += 1; + max_table_size = max(max_table_size, sets[realDestination].size); + } else { + sets[realSource].size += sets[realDestination].size; + sets[realDestination].size = 0; + sets[realDestination].parent = realSource; + max_table_size = max(max_table_size, sets[realSource].size); + } + } + } }; int main() { |