Algorithms : complete 02-data_structures 02-priority_queues_and_disjoint_sets

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() {